Why color a graph?
Suppose tasks that share a resource cannot run simultaneously. Make each task a vertex and join conflicting tasks by an edge. A color represents a time slot: adjacent vertices must receive different colors. Minimizing colors then minimizes slots in this model. The graph records pairwise conflicts only; further scheduling restrictions require further modeling.
Definition 5.3.1
(Proper coloring and chromatic number)
Let be a finite simple undirected graph. A proper -coloring is a map such that for every edge . The chromatic number is the least such ; set for the empty graph. A clique is a set of pairwise adjacent vertices. Write for the maximum degree when is nonempty.
The color classes are independent sets, some possibly empty if the palette is larger than necessary; the nonempty classes form a partition of the vertices. Every clique of size needs distinct colors, so . This is a lower bound, not automatically an equality: other edges can force additional colors.
Concept lensStructural
Colorings as maps into a complete graph
A proper -coloring is the same thing as a graph homomorphism , that is, a map on vertices sending every edge to an edge. The vertices of are the colors, and two colors are adjacent exactly when they differ, so “edges go to edges” says precisely that adjacent vertices get different colors. In this language is the least admitting a homomorphism , and a graph is two-colorable exactly when it maps to .
The description composes. If is a homomorphism and is a proper coloring, then is a proper coloring of , so . The inclusion of a subgraph gives , and the inclusion of an -clique gives the clique bound .
Greedy coloring
Choose an ordering . At step , assign the least positive integer not used on its already colored neighbors. Later neighbors cannot invalidate this choice, because when each is colored it avoids the color of .
Theorem 5.3.2
(Greedy degree bound)
For every nonempty finite simple graph, greedy coloring in any vertex order is proper and uses at most colors. More precisely, if each vertex has at most earlier neighbors in the chosen order, at most colors are used.
Proof
(Counting forbidden colors)
At step at most colors are forbidden by earlier neighbors. Among at least one is available. Every edge has a later endpoint, and that endpoint avoids the earlier endpoint's color. Hence the final coloring is proper. Since no vertex has more than neighbors, the stated bound follows. An order with fewer earlier neighbors can give a better bound; it need not give the optimum.
Worked example 5.3.3
(A cycle and an optimality certificate)
On the cycle , process vertices in cyclic order. Greedy assigns . The first four assignments alternate, and the final vertex sees both colors. Three colors suffice. Two cannot suffice: alternating around the first four edges forces to have the same color as , although they are adjacent. Thus even though its largest clique has size .
Two colors and odd cycles
Definition 5.3.4
(Bipartite graph)
A graph is bipartite if its vertex set can be partitioned as with no edge having both endpoints in or both in . Either part may be empty.
Both parts are independent sets. Giving color 1 and color 2 produces a proper two-coloring; conversely, the two color classes of any proper two-coloring give such a partition. Bipartiteness and two-colorability therefore express the same property, one as a partition and the other as an assignment of labels.
Theorem 5.3.5
(Bipartite criterion)
A finite simple graph is 2-colorable if and only if it has no odd cycle. Here 2-colorable means that a palette of two colors suffices, including for an edgeless or empty graph.
Proof
(Parity of breadth-first distances)
In a proper two-coloring, colors alternate along every path. An odd cycle would return to its start with the opposite color, impossible.
Conversely, assume there is no odd cycle. Work in each connected component, choose a root , and choose one BFS parent tree. Each tree path from is a shortest path. Write for its length and put each vertex in the class given by the parity of . If is an edge, appending that edge to a shortest path to gives ; reversing the roles gives . Thus adjacent distances differ by at most one, and adjacent vertices of the same parity must have equal distance, say .
Suppose such an edge existed. The two tree paths share an initial segment ending at their last common ancestor, at some distance from . Beyond that ancestor their tails have no common vertex and each has length . Those tails and the edge form a simple cycle of length . It is odd, a contradiction. Every edge therefore joins opposite parity classes. Color the classes differently. Isolated vertices cause no difficulty. This works separately in every component.
Proof X-ray
Where the absence of odd cycles is used
The forward direction needs only that colors alternate along each edge. The converse rests on two moves. First, the distance inequality on every edge turns “same parity” into the equality ; parity alone would not show that the two tree paths have equal length. Second, stopping at the last common ancestor makes the two tails meet only there, so tail, edge and reversed tail form a simple cycle rather than a closed walk that might repeat vertices. Since , we have , and the hypothesis is used exactly once, to forbid that cycle of odd length . The argument is run in each component separately because is defined only on the component of .
Worked example 5.3.6
(Greedy depends on order)
Let the edges be (a path on four vertices). In the order , greedy gives . Yet the coloring , is proper. Thus a greedy run gives an upper bound, not a proof that its number of colors is minimal.
Obtaining a useful order by removal
The sharper earlier-neighbor bound suggests how to choose an order. Suppose every nonempty subgraph has a vertex of degree at most within that subgraph. Repeatedly remove such a vertex, recording the removal order, until no vertices remain. Then color in the reverse order. When a removed vertex is restored, its already restored neighbors are precisely its neighbors that remained at its removal, at most . Greedy therefore uses at most colors. The degree here is measured in the current subgraph, not necessarily in the original graph.
For instance, every nonempty subgraph of a forest has a vertex of degree at most one: a nontrivial tree has a leaf, while an isolated vertex has degree zero. The removal argument gives a two-coloring of every forest. An edgeless forest needs only one color if nonempty; a forest containing an edge needs two. This recovers the exact answer without asserting that every order of its vertices uses only two colors, which the four-vertex path example disproves.
Worked example 5.3.7
(Why the removal order must be reversed)
Return to the path . Remove , then , then , then . Their degrees when removed are respectively . In particular, originally had degree two, but only its neighbor remains when is removed. Color in the reverse order . The assignments are : when restored, and each see only , while sees only . Each vertex has at most one earlier neighbor, so the two-color bound applies.
Coloring in the removal order instead gives the earlier three-color example. A low degree at removal counts neighbors that remain after removal. Those are earlier colored neighbors only when the removal order is reversed. Recording small residual degrees without reversing the order would not justify the claimed bound.
From a theorem to a certificate
A claim that a graph is -colorable can be checked by inspecting the colors of all edges. A claim that it needs at least colors asks for different evidence. A -clique is one such certificate, but the five-cycle shows it is not the only possible one. In that example the odd cycle rules out two colors and an explicit three-coloring supplies the matching upper bound. Both halves are needed to establish the exact value. A failed attempt to find a two-coloring is not by itself a proof of impossibility.
Worked example 5.3.8
(Matching an upper and a lower bound)
Take a triangle with vertices , and add a vertex adjacent to and but not . The triangle needs three colors. Assign ; the only neighbor of with color 3 would have been , and that edge is absent. Thus three colors suffice and the lower bound is attained: . Counting four vertices alone would provide the weaker upper bound four, while the triangle alone would give only the lower bound.
The empty graph deserves a separate convention. When , there is a unique empty coloring with no colors, so . A nonempty graph without edges has chromatic number . For a disconnected nonempty graph, its chromatic number is the maximum of the chromatic numbers of its components: every component inherits any coloring of the whole graph, while optimal component colorings can reuse the same palette. It is not the sum of the component chromatic numbers.
Finding a coloring or an odd cycle
Breadth-first search (BFS) provides a practical version of the parity proof. In each unvisited component, choose a root, assign it distance zero and explore its neighbors, recording a parent when a vertex is first discovered. Each vertex receives the parity of its BFS distance. If every edge joins different parities, those parities give a proper two-coloring. An edge whose endpoints have the same parity is a certificate of failure: since adjacent distances differ by at most one, the two distances are in fact equal. Follow parent links from both endpoints to their last common ancestor; the two remaining tree paths and the offending edge form an odd cycle.
Worked example 5.3.9
(Constructing the odd cycle)
Consider edges and start BFS at . The distances are at , at , and at . The edge joins vertices of equal parity. The parent paths are and , with last common ancestor . Together with they give , a cycle of length five. This is a checkable reason that no two-coloring exists; the assignment of BFS parents alone would not be a contradiction until the edge is examined.
With adjacency lists, BFS processes each vertex and each edge only a constant number of times, so the test takes time. If the graph is disconnected, restarting at every unvisited vertex is essential: testing only the root's component could miss an odd cycle elsewhere. With an adjacency matrix, scanning every possible neighbor takes time instead. These are implementation bounds for the graph representation stated, not a claim about the cost of obtaining the graph data.
How bad can the order be?
A poor greedy order is not limited to wasting one extra color. For , take vertices and put an edge exactly when . The two sets of 's and 's give a proper two-coloring, and an edge exists, so the chromatic number is two. Now process . Inductively, both and receive color : each sees all earlier colors on vertices of the opposite type, while and are not adjacent. Thus greedy uses colors despite the optimal two. This example explains why a color count from a particular ordering is an upper bound rather than an optimality certificate.
The degree bound remains valid here: every vertex has degree , so greedy uses exactly . A sharp upper bound for a particular algorithm therefore does not say that the graph's chromatic number must attain that bound. To prove a better result for a given graph, seek either a better order or a coloring constructed by another argument, and pair it with a lower bound.
Only complete graphs and odd cycles: every other connected graph can be colored with at most the maximum degree.
A natural next question
Which connected graphs actually need one more color than the maximum degree?
Only complete graphs and odd cycles: every other connected graph can be colored with at most the maximum degree.
Complete graphs and odd cycles (where ) need colors. Brooks' theorem says that these are the only connected examples: a connected graph that is neither complete nor an odd cycle satisfies . Its proof is again a greedy coloring, in a carefully chosen order whose last vertex sees a repeated color among its neighbors. The bound can still be far from , as the star in the common mistakes shows.
Common mistakes
Common mistake
(Degree counts neighbors, not forbidden colors)
The number of neighbors is not necessarily the number of forbidden colors. In a star with center and leaves, the center has degree , but all leaves can share one color because no two leaves are adjacent. Give the leaves color 1 and the center color 2. An edge rules out one color, so the chromatic number is exactly two, even for very large . The degree bound is useful because the number of distinct forbidden colors is at most the number of earlier neighbors; it does not require those neighbors to have different colors.
Common mistake
(Two-colorable is not the same as chromatic number two)
“Two-colorable” means that two available colors suffice, not that both must appear. A nonempty edgeless graph is two-colorable although its chromatic number is one; the bipartite criterion characterizes , and holds exactly when, in addition, the graph has an edge.
The bipartite criterion also invites a tempting shortcut, which a five-vertex graph refutes.
Counterexample mode
Excluding triangles does not exclude odd cycles
Claim: a graph with no triangle is two-colorable. Take with vertices in cyclic order. Each vertex has exactly two neighbors, and (indices mod ), and these are not adjacent, so no triangle exists. Yet a two-coloring would alternate along , giving a color different from , hence equal to that of , while is an edge. So is not two-colorable. The repair is the full hypothesis of the criterion: every odd cycle, not only those of length three, must be excluded, or a valid partition must be exhibited.
Exercises
Quick check
(Find for and justify both bounds.)
Solution · Answer
All vertices form a clique, so at least colors are needed; giving each vertex a distinct color uses . Hence .
Quick check
(A graph has maximum degree and contains a triangle. What bounds follow? Give an example attaining each endpoint.)
Solution · Answer
The triangle gives and greedy gives . A triangle with a pendant vertex has maximum degree and is 3-colorable; has maximum degree and needs 4 colors.
Quick check
(Greedy-color the path in order . Explain why two colors are necessary.)
Solution · Answer
The colors are . Since the graph has an edge, one color is impossible; consequently its chromatic number is .
Quick check
(A graph consists of , a triangle and an isolated vertex as separate components. Find its chromatic number.)
Solution · Answer
The components have chromatic numbers . Reuse the same three colors on each component; supplies the lower bound three. Thus the answer is , not .
Quick check
(A BFS rooted at has parent edges and another edge . Exhibit an odd cycle. Why can this conclusion be drawn from the edge, rather than merely from the parent tree?)
Solution · Answer
The cycle is , of length five. The tree itself has no cycle; the extra edge closes the two parent paths.
Quick check
(For the graph with edges , determine its chromatic number.)
Solution · Answer
The vertices form a triangle, so at least three colors are required. Set . Since and are not adjacent, this is proper, giving .