Graph coloring

Let's return now to the subject of , assigning frequencies to radio stations so that they don't interfere. The first thing that we will need to do is to turn the map of radio stations into a suitable graph, which should be pretty natural at this juncture. We define a graph \(\GVE\) in which \(V\) is the set of radio stations and \(xy\in E\) if and only if radio station \(x\) and radio station \(y\) are within \(200\) miles of each other. With this as our model, then we need to assign different frequencies to two stations if their corresponding vertices are joined by an edge. This leads us to our next topic, coloring graphs.

When \(\GVE\) is a graph and \(C\) is a set of elements called colors, a proper coloring of \(\bfG\) is a function \(\phi:V\to C\) such that \(\phi(x)\neq \phi(y)\) whenever \(xy\) is an edge in \(\bfG\). The least \(t\) for which \(\bfG\) has a proper coloring using a set \(C\) of \(t\) colors is called the chromatic number of \(\bfG\) and is denoted \(\chi(\bfG)\) \(\chi(\bfG)\) chromatic number of a graph \(\bfG\) . In , we show a proper coloring of a graph using \(5\) colors. Now we can see that our radio frequency assignment problem is the much-studied question of finding the chromatic number of an appropriate graph.

A graph \(\GVE\) with \(\chi(\bfG)\le 2\) is called a \(2\)-colorable graph. A couple of minutes of reflection should convince you that for \(n\geq 2\), the cycle \(\bfC_{2n}\) with \(2n\) vertices is \(2\)-colorable. On the other hand, \(\bfC_3\cong \bfK_3\) is clearly not \(2\)-colorable. Furthermore, no odd cycle \(\bfC_{2n+1}\) for \(n\geq 1\) is \(2\)-colorable. It turns out that the property of containing an odd cycle is the only impediment to being \(2\)-colorable, which means that recognizing \(2\)-colorable graphs is easy, as the following theorem shows.

A graph \(\bfG\) is called a bipartite graph when there is a partition of the vertex set \(V\) into two sets \(A\) and \(B\) so that the subgraphs induced by \(A\) and \(B\) are independent graphs, , no edge of \(\bfG\) has both of its endpoints in \(A\) or in \(B\). Evidently, bipartite graphs are \(2\)-colorable. On the other hand, when a \(2\)-colorable graph is disconnected, there is more than one way to define a suitable partition of the vertex set into two independent sets.

Bipartite graphs are commonly used as models when there are two distinct types of objects being modeled and connections are only allowed between two objects of different types. For example, on one side, list candidates who attend a career fair and on the other side list the available positions. The edges might naturally correspond to candidate/position pairs which link a person to a responsibility they are capable of handling.

As a second example, a bipartite graph could be used to visualize the languages spoken by a group of students. The vertices on one side would be the students with the languages listed on the other side. We would then have an edge \(xy\) when student \(x\) spoke language \(y\). A concrete example of this graph for our favorite group of students is shown in , although Alice isn't so certain there should be an edge connecting Dave and English.

One special class of bipartite graphs that bears mention is the class of complete bipartite graphs. The complete bipartite graph \(\bfK_{m,n}\) has vertex set \(V=V_1\cup V_2\) with \(|V_1|=m\) and \(|V_2|=n\). It has an edge \(xy\) if and only if \(x\in V_1\) and \(y\in V_2\). The complete bipartite graph \(\bfK_{3,3}\) is

Condensed: the full section is in Keller & Trotter, Applied Combinatorics.

A clique in a graph \(\GVE\) is a set \(K\subseteq V\) such that the subgraph induced by \(K\) is isomorphic to the complete graph \(\bfK_{|K|}\). Equivalently, we can say that every pair of vertices in \(K\) are adjacent. The maximum clique size or clique number of a graph \(\bfG\), denoted \(\omega(\bfG)\) \(\omega(\bfG)\) clique number of \(\bfG\) , is the largest \(t\) for which there exists a clique \(K\) with \(|K|=t\). For example, the graph in has clique number \(4\) while the graph in has maximum clique size\(2\).

For every graph \(\bfG\), it is obvious that \(\chi(\bfG)\ge \omega(\bfG)\). On the other hand, the inequality may be far from tight. Before showing how bad it can be, we need to introduce a more general version of the . Consider a function \(f\colon X\to Y\) with \(|X| = 2|Y|+1\). Since \(|X|>|Y|\), the Pigeon Hole Principle as stated in only tells us that there are distinct \(x,x'\in X\) with \(f(x)=f(x')\). However, we can say more here. Suppose that each element of \(Y\) has at most two elements of \(X\) mapped to it. Then adding up the number of elements of \(X\) based on how many are mapped to each element of \(Y\) would only allow \(X\) to have (at most) \(2|Y|\) elements. Thus, there must be \(y\in Y\) so that there are three distinct elements \(x,x',x''\in X\) with \(f(x)=f(x')=f(x'')=y\). This argument generalizes to give the following version of the Pigeon Hole Principle:

We are now prepared to present the following proposition showing that clique number and chromatic number need not be close at all. We give two proofs. The first is the work of J. Kelly and L. Kelly, while the second is due to J. Mycielski.

Since a \(3\)-clique looks like a triangle, is often stated as There exist triangle-free graphs with large chromatic number. As an illustration of the construction in the proof of Mycielski, we again The graph shown is \(\bfG_4\). We will return to the topic of graphs with large chromatic number in where we show that there are graphs with large chromatic number which lack not only cliques of more than two vertices but also cycles of fewer than \(g\) vertices for any value of \(g\). In other words, there is a graph \(\bfG\) with \(\chi(\bfG)=10^6\) but no cycle with fewer than \(10^{10}\) vertices!

Condensed: the full section is in Keller & Trotter, Applied Combinatorics.

Suppose you are given a graph \(\bfG\). It's starting to look like it is not easy to find an algorithm that answers the question Is \(\chi(\bfG)\leq t\)? It's easy to verify a certificate (a proper coloring using at most \(t\) colors), but how could you even find a proper coloring, not to mention one with the fewest number of colors? Similarly for the question Is \(\omega(\bfG)\geq k\)?, it is easy to verify a certificate. However, finding a maximum clique appears to be a very hard problem. Of course, since the gap between \(\chi(\bfG)\) and \(\omega(\bfG)\) can be arbitrarily large, being able to find one value would not (generally) help in finding the value of the other. No polynomial-time algorithm is known for either of these problems, and many believe that no such algorithm exists. In this subsection, we look at one approach to finding chromatic number and see a case where it does work efficiently.

A very naïve algorithmic way to approach graph coloring is the First Fit, or greedy, algorithm. For this algorithm, fix an ordering of the vertex set \(V=\{v_1,v_2,\dots v_n\}\). We define the coloring function \(\phi\) one vertex at a time in increasing order of subscript. We begin with \(\phi(v_1)=1\) and then we define \(\phi(v_{i+1})\) (assuming vertices \(v_1,v_2,\dots,v_i\) have been colored) to be the least positive integer color that has not already been used on any of its neighbors in the set \(\{v_1,\dots v_i\}\).

shows two different orderings of the same graph. demonstrates that the ordering of \(V\) is vital to the ability of the First Fit algorithm to color \(\bfG\) using \(\chi(\bfG)\) colors. In general, finding an optimal ordering is just as difficult as coloring \(\bfG\). Thus, this very simple algorithm does not work well in general. However, for some classes of graphs, there is a natural ordering that leads to optimal performance of First Fit. Here is one such exampleone that we will study again in the next chapter in a different context.

A graph \(\bfG\) is said to be perfect if \(\chi(\bfH)=\omega(\bfH)\) for every induced subgraph \(\bfH\). Since an induced subgraph of an interval graph is an interval graph, shows interval graphs are perfect. The study of perfect graphs originated in connection with the theory of communications networks and has proved to be a major area of research in graph theory for many years now.

Condensed: the full section is in Keller & Trotter, Applied Combinatorics.

In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring is a special case of graph labeling. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face (or region) so that no two faces that share a boundary have the same color.

Vertex coloring is often used to introduce graph coloring problems, since other coloring problems can be transformed into a vertex coloring instance. For example, an edge coloring of a graph is just a vertex coloring of its line graph, and a face coloring of a plane graph is just a vertex coloring of its dual. However, non-vertex coloring problems are often stated and studied as-is. This is partly pedagogical, and partly because some problems are best studied in their non-vertex form, as in the case of edge coloring.

The convention of using colors originates from coloring the countries in a political map, where each face is literally colored. This was generalized to coloring the faces of a graph embedded in the plane. By planar duality it became coloring the vertices, and in this form it generalizes to all graphs. In mathematical and computer representations, it is typical to use the first few positive or non-negative integers as the "colors". In general, one can use any finite set as the "color set". The nature of the coloring problem depends on the number of colors but not on what they are.

Graph coloring enjoys many practical applications as well as theoretical challenges. Beside the classical types of problems, different limitations can also be set on the graph, or on the way a color is assigned, or even on the color itself. It has even reached popularity with the general public in the form of the popular number puzzle Sudoku. Graph coloring is still a very active field of research.

The first results about graph coloring deal almost exclusively with planar graphs in the form of map coloring. While trying to color a map of the counties of England in 1852, Francis Guthrie postulated the four color conjecture, noting that four colors were sufficient to color the map so that no regions sharing a common border received the same color. Guthrie's brother Frederick passed on the question to his mathematics teacher Augustus De Morgan at University College, who mentioned it in a letter to William Hamilton in 1852. Arthur Cayley raised the problem at a meeting of the London Mathematical Society in 1879. The same year, Alfred Kempe published a paper that claimed to establish the result, and for a decade the four color problem was considered solved. For his accomplishment Kempe was elected a Fellow of the Royal Society and later President of the London Mathematical Society.

In 1890, Percy John Heawood pointed out that Kempe's argument was wrong. However, in that paper he proved the five color theorem, saying that every planar map can be colored with no more than five colors, using ideas of Kempe. In the following century, a vast amount of work was done and theories were developed to reduce the number of colors to four, until the four color theorem was finally proved in 1976 by Kenneth Appel and Wolfgang Haken. The proof went back to the ideas of Heawood and Kempe and largely disregarded the intervening developments. The proof of the four color theorem is noteworthy, aside from its solution of a century-old problem, for being the first major computer-aided proof.

In 1912, George David Birkhoff introduced the chromatic polynomial to study the coloring problem, which was generalised to the Tutte polynomial by W. T. Tutte, both of which are important invariants in algebraic graph theory. Kempe had already drawn attention to the general, non-planar case in 1879, and many results on generalisations of planar graph coloring to surfaces of higher order followed in the early 20th century.

In 1960, Claude Berge formulated another conjecture about graph coloring, the strong perfect graph conjecture, originally motivated by an information-theoretic concept called the zero-error capacity of a graph introduced by Shannon. The conjecture remained unresolved for 40 years, until it was established as the celebrated strong perfect graph theorem by Chudnovsky, Robertson, Seymour, and Thomas in 2002.

Graph coloring has been studied as an algorithmic problem since the early 1970s: the chromatic number problem (see section § Vertex coloring below) is one of Karp's 21 NP-complete problems from 1972, and at approximately the same time various exponential-time algorithms were developed based on backtracking and on the deletion-contraction recurrence of Zykov (1949). One of the major applications of graph coloring, register allocation in compilers, was introduced in 1981.

When used without any qualification, a coloring of a graph almost always refers to a proper vertex coloring, namely a labeling of the graph's vertices with colors such that no two vertices sharing the same edge have the same color. Since a vertex with a loop (i.e. a connection directly back to itself) could never be properly colored, it is understood that graphs in this context are loopless.

The terminology of using colors for vertex labels goes back to map coloring. Labels like red and blue are only used when the number of colors is small, and normally it is understood that the labels are drawn from the integers {1, 2, 3, ...}.

A coloring using at most k colors is called a (proper) k-coloring. The smallest number of colors needed to color a graph G is called its chromatic number, and is often denoted χ(G). Sometimes γ(G) is used, since χ(G) is also used to denote the Euler characteristic of a graph. A graph that can be assigned a (proper) k-coloring is k-colorable, and it is k-chromatic if its chromatic number is exactly k. A subset of vertices assigned to the same color is called a color class; every such class forms an independent set. Thus, a k-coloring is the same as a partition of the vertex set into k independent sets, and the terms k-partite and k-colorable have the same meaning.

The chromatic polynomial counts the number of ways a graph can be colored using some of a given number of colors. For example, using three colors, the graph in the adjacent image can be colored in 12 ways. With only two colors, it cannot be colored at all. With four colors, it can be colored in 24 + 4 × 12 = 72 ways: using all four colors, there are 4! = 24 valid colorings (every assignment of four colors to any 4-vertex graph is a proper coloring); and for every choice of three of the four colors, there are 12 valid 3-colorings. So, for the graph in the example, a table of the number of valid colorings would start like this:

The chromatic polynomial is a function P(G, t) that counts the number of t-colorings of G. As the name indicates, for a given G the function is indeed a polynomial in t. For the example graph, P(G, t) = t(t − 1)(t − 2), and indeed P(G, 4) = 72.

The chromatic polynomial includes more information about the colorability of G than does the chromatic number. Indeed, χ is the smallest positive integer that is not a zero of the chromatic polynomial χ(G) = min{k : P(G, k) > 0}.

An edge coloring of a graph is a proper coloring of the edges, meaning an assignment of colors to edges so that no vertex is incident to two edges of the same color. An edge coloring with k colors is called a k-edge-coloring and is equivalent to the problem of partitioning the edge set into k matchings. The smallest number of colors needed for an edge coloring of a graph G is the chromatic index, or edge chromatic number, χ′(G). A Tait coloring is a 3-edge coloring of a cubic graph. The four color theorem is equivalent to the assertion that every planar cubic bridgeless graph admits a Tait coloring.

Total coloring is a type of coloring on the vertices and edges of a graph. When used without any qualification, a total coloring is always assumed to be proper in the sense that no adjacent vertices, no adjacent edges, and no edge and its end-vertices are assigned the same color. The total chromatic number χ″(G) of a graph G is the fewest colors needed in any total coloring of G.

For a graph G with a strong embedding on an orientable surface, William T. Tutte discovered that if the graph is k-face-colorable then G admits a nowhere-zero k-flow. The equivalence holds if the surface is sphere.

An unlabeled coloring of a graph is an orbit of a coloring under the action of the automorphism group of the graph. The colors remain labeled; it is the graph that is unlabeled. There is an analogue of the chromatic polynomial which counts the number of unlabeled colorings of a graph from a given finite color set.

If we interpret a coloring of a graph on d vertices as a vector in ⁠\(\mathbb{Z}^d\)⁠, the action of an automorphism is a permutation of the coefficients in the coloring vector.

Assigning distinct colors to distinct vertices always yields a proper coloring, so

\(1 \le \chi(G) \le n.\)

The only graphs that can be 1-colored are edgeless graphs. A complete graph \(K_n\) of n vertices requires \(\chi(K_n)=n\) colors. In an optimal coloring there must be at least one of the graph's m edges between every pair of color classes, so

\(\chi(G)(\chi(G)-1) \le 2m.\)

More generally a family \(\mathcal{F}\) of graphs is χ-bounded if there is some function \(c\) such that the graphs \(G\) in \(\mathcal{F}\) can be colored with at most \(c(\omega(G))\) colors, where \(\omega(G)\) is the clique number of \(G\). For the family of the perfect graphs this function is \(c(\omega(G))=\omega(G)\).

The 2-colorable graphs are exactly the bipartite graphs, including trees and forests. By the four color theorem, every planar graph can be 4-colored.

A greedy coloring shows that every graph can be colored with one more color than the maximum vertex degree,

\(\chi(G) \le \Delta(G) + 1.\)

Complete graphs have \(\chi(G)=n\) and \(\Delta(G)=n-1\), and odd cycles have \(\chi(G)=3\) and \(\Delta(G)=2\), so for these graphs this bound is best possible. In all other cases, the bound can be slightly improved; Brooks' theorem states that

Brooks' theorem: \(\chi (G) \le \Delta (G)\) for a connected, simple graph G, unless G is a complete graph or an odd cycle.

Several lower bounds for the chromatic number have been discovered over the years:

If G contains a clique of size k, then at least k colors are needed to color that clique; in other words, the chromatic number is at least the clique number:

\(\chi(G) \ge \omega(G).\)

For perfect graphs this bound is tight. Finding cliques is known as the clique problem.

Hoffman's bound: Let \(W\) be a real symmetric matrix such that \(W_{i,j} = 0\) whenever \((i,j)\) is not an edge in \(G\). Define \(\chi_W(G) = 1 - \tfrac{\lambda_{\max}(W)}{\lambda_{\min}(W)}\), where \(\lambda_{\max}(W), \lambda_{\min}(W)\) are the largest and smallest eigenvalues of \(W\). Define \(\chi_H(G) = \max_W \chi_W(G)\), with \(W\) as above. Then:

\(\chi_H(G)\leq \chi(G).\)

Vector chromatic number: Let \(W\) be a positive semi-definite matrix such that \(W_{i,j} \le -\tfrac{1}{k-1}\) whenever \((i,j)\) is an edge in \(G\). Define \(\chi_V(G)\) to be the least k for which such a matrix \(W\) exists. Then

\(\chi_V(G)\leq \chi(G).\)

Lovász number: The Lovász number of a complementary graph is also a lower bound on the chromatic number:

\(\vartheta(\bar{G}) \leq \chi(G).\)

Fractional chromatic number: The fractional chromatic number of a graph is a lower bound on the chromatic number as well:

\(\chi_f(G) \leq \chi(G).\)

\(\chi_H(G) \leq \chi_V(G) \leq \vartheta(\bar{G}) \leq \chi_f(G) \leq \chi(G).\)

Condensed: the full section is in Wikipedia.

Graphs with large cliques have a high chromatic number, but the opposite is not true. The Grötzsch graph is an example of a 4-chromatic graph without a triangle, and the example can be generalized to the Mycielskians.

Theorem (W. T. Tutte, 1947, Alexander Zykov 1949, Jan Mycielski 1955): There exist triangle-free graphs with arbitrarily high chromatic number.

To prove this, both, Mycielski and Zykov, each gave a construction of an inductively defined family of triangle-free graphs but with arbitrarily large chromatic number. Burling (1965) constructed axis aligned boxes in \(\mathbb{R}^{3}\) whose intersection graph is triangle-free and requires arbitrarily many colors to be properly colored. This family of graphs is then called the Burling graphs. The same class of graphs is used for the construction of a family of triangle-free line segments in the plane, given by Pawlik et al. (2014). It shows that the chromatic number of its intersection graph is arbitrarily large as well. Hence, this implies that axis aligned boxes in \(\mathbb{R}^{3}\) as well as line segments in \(\mathbb{R}^{2}\) are not χ-bounded.

From Brooks's theorem, graphs with high chromatic number must have high maximum degree. But colorability is not an entirely local phenomenon: A graph with high girth looks locally like a tree, because all cycles are long, but its chromatic number need not be 2:

Theorem (Erdős): There exist graphs of arbitrarily high girth and chromatic number.

An edge coloring of G is a vertex coloring of its line graph \(L(G)\), and vice versa. Thus,

\(\chi'(G)=\chi(L(G)).\)

There is a strong relationship between edge colorability and the graph's maximum degree \(\Delta(G)\). Since all edges incident to the same vertex need their own color, we have

\(\chi'(G) \ge \Delta(G).\)

Moreover,

Kőnig's theorem: \(\chi'(G) = \Delta(G)\) if G is bipartite.

In general, the relationship is even stronger than what Brooks's theorem gives for vertex coloring:

Vizing's Theorem: A graph of maximal degree \(\Delta\) has edge-chromatic number \(\Delta\) or \(\Delta+1\).

A graph has a k-coloring if and only if it has an acyclic orientation for which the longest path has length at most k; this is the Gallai-Hasse-Roy-Vitaver theorem (Nešetřil & Ossona de Mendez 2012).

For planar graphs, vertex colorings are essentially dual to nowhere-zero flows.

About infinite graphs, much less is known. The following are two of the few results about infinite graph coloring:

• If all finite subgraphs of an infinite graph G are k-colorable, then so is G, under the assumption of the axiom of choice. This is the de Bruijn-Erdős theorem of de Bruijn & Erdős (1951).
• If a graph admits a full n-coloring for every n ≥ n₀, it admits an infinite full coloring (Fawcett 1978).

As stated above, \(\omega(G) \le \chi(G) \le \Delta(G) + 1.\) A conjecture of Reed from 1998 is that the value is essentially closer to the lower bound, \(\chi(G) \le \left\lceil \frac{\omega(G) + \Delta(G) + 1}{2} \right\rceil.\)

The chromatic number of the plane, where two points are adjacent if they have unit distance, is unknown, although it is one of 5, 6, or 7. Other open problems concerning the chromatic number of graphs include the Hadwiger conjecture stating that every graph with chromatic number k has a complete graph on k vertices as a minor, the Erdős-Faber-Lovász conjecture bounding the chromatic number of unions of complete graphs that have at most one vertex in common to each pair, and the Albertson conjecture that among k-chromatic graphs the complete graphs are the ones with smallest crossing number.

When Birkhoff and Lewis introduced the chromatic polynomial in their attack on the four color theorem, they conjectured that for planar graphs \(G\), the polynomial \(P(G,t)\) has no zeros in the region \([4,\infty)\). Although it is known that such a chromatic polynomial has no zeros in the region \([5,\infty)\) and that \(P(G,4) \neq 0\), their conjecture is still unresolved. It also remains an unsolved problem to characterize graphs which have the same chromatic polynomial and to determine which polynomials are chromatic.