A graph coloring is an assignment of labels, called colors, to the vertices of a graph such that no two adjacent vertices share the same color. The chromatic number of a graph is the minimal number of colors for which such an assignment is possible. Other types of colorings on graphs also exist, most notably edge colorings that may be subject to various constraints.
The study of graph colorings has historically been linked closely to that of planar graphs and the four color theorem, which is also the most famous graph coloring problem. That problem provided the original motivation for the development of algebraic graph theory and the study of graph invariants such as those discussed on this page. In modern times, many open problems in algebraic graph theory deal with the relation between chromatic polynomials and their graphs. Applications for solved problems have been found in areas such as computer science, information theory, and complexity theory. Many day-to-day problems, like minimizing conflicts in scheduling, are also equivalent to graph colorings.
Sudoku can be seen as a graph coloring problem, where the squares of the grid are vertices and the numbers are colors that must be different if in the same row, column, or grid (such vertices in the graph are connected by an edge). The sudoku is then a graph of 81 vertices and chromatic number 9. How many edges does this 81-vertex graph have?
The chromatic number of a graph is the minimal number of colors for which a graph coloring is possible. This definition is a bit nuanced though, as it is generally not immediate what the minimal number is. For certain types of graphs, such as complete () or bipartite (), there are very few choices possible, and so it is possible to determine, for instance, that since each vertex must have a different color than the rest. The minimality component of chromatic numbers is useful for proving many basic theorems quickly, as it allows a focus on extreme, instead of general, cases (here, graph colorings that minimize the number of colors). It is for precisely that reason that mathematicians prefer such definitions.
A graph is called -colorable if there exists a graph coloring on with colors. If a graph is -colorable, then it is -colorable for any . A graph has a chromatic number that is at least as large as the chromatic number of any of its subgraphs. A graph has a chromatic number that is at most one larger than the chromatic number of a subgraph containing only one less vertex.
Consider the cyclic graph where . Prove that
Suppose is even. Then, since there are two adjacent edges in . But a graph coloring for exists where vertices are alternately colored red and blue, so .
Suppose is odd. Then, since there are two adjacent edges in . Furthermore, since vertex colors cannot alternate, as the final vertex to be colored will be adjacent to both a red and a blue vertex. But a graph coloring for exists where vertices are alternately colored red and blue and the final vertex is colored yellow, so .
Suppose a graph and a graph are combined to create a graph by connecting each vertex of to each vertex of and otherwise all vertices and edges remaining unchanged. Prove that
Let have a graph coloring with colors and have a graph coloring with colors . Then, color the vertices in from and accordingly with colors . Since no vertices of and are the same color, this constitutes a graph coloring of , implying .
Now, consider a minimal graph coloring of . Suppose there are colors among the vertices from , and suppose there are colors among the vertices from . Because every vertex in is adjacent to every vertex in , the two vertex sets cannot have any color in common. So this graph coloring of has precisely colors. But note that and as otherwise the chromatic number would not be minimal (the subgraph of vertices from in is precisely ; likewise for ). So .
It follows that
The chromatic polynomial of a graph is a polynomial that, for each natural number , returns the number of -colorings of . is the smallest positive integer that is not a root of . The degree of is equal to the number of vertices of .
Consider an acyclic graph on vertices (also known as a tree). Prove that .
Consider an arbitrary vertex of . There are possible colors for it. Now, consider each of its neighbors; there are possible colors for each of them. Then, the neighbors of each of those vertices also has possible colors, and so on. There will never be any further restrictions on a vertex's color, since the graph contains no cycles. Thus, there are choices for the first vertex and choices for each of the subsequent vertices; there are a total of choices.
The most common type of edge coloring is analogous to graph (vertex) colorings. Each edge of a graph has a color assigned to it in such a way that no two adjacent edges are the same color. Such a coloring is a proper edge coloring. With cycle graphs, the analogy becomes an equivalence, as there is an edge-vertex duality. In general, however, the chromatic number is not related to the minimal such that a proper edge -coloring exists.
Another type of edge coloring is used in Ramsey theory and similar problems. In such cases, edges of the graph are colored one of colors and mathematicians investigate the resulting colored graph substructures to determine what sizes of complete subgraphs exist.
A final type of edge coloring is used in the study of spanning trees. Edges are colored in such a way that there does not exist a cycle of the same color, and the minimal number of colors required for such an edge coloring of a given graph is known as its arboricity.
Prove that any planar graph has an edge coloring of at most three colors in which adjacent edges of the same color are allowed but cycles of edges of the same color are not.