The Maximum-Degree Plus One Bound

The Bound and Its Key Counting Idea

Greedy coloring makes each decision using only the vertices that have already been colored. The choice of vertex order can affect the result, but there is a limit that holds for every order: no vertex can be blocked by more colors than it has neighbors. This gives a general upper bound on the number of colors needed, even when the order is not chosen carefully.

All graphs in this tutorial are finite and simple. A proper vertex coloring assigns a color to each vertex so that the endpoints of every edge have different colors. The chromatic number \(\chi(G)\) is the smallest number of colors in any proper coloring of \(G\). For a nonempty graph, \(\Delta(G)\) is its maximum vertex degree: the largest number of neighbors of any one vertex.

The word “distinct” matters. A vertex may have several already colored neighbors, but if some of them share a color, that color is forbidden only once. In any case, the number of forbidden colors is at most the number of already colored neighbors, which is at most the vertex’s degree.

An Order-Specific Bound

Before using the maximum degree, it helps to record exactly what the chosen order contributes. For each vertex, count its neighbors that occur earlier in the order. Let \(k\) be the largest of these counts.

Proof. Process the vertices in the given order, using the greedy rule. Suppose \(v_i\) has \(r_i\) earlier neighbors. Only those \(r_i\) vertices can forbid colors at the step for \(v_i\), since later vertices have not yet been colored. Thus the set of forbidden colors has at most \(r_i\) elements. Since \(r_i\leq k\), at most \(k\) colors are forbidden. Among the \(k+1\) colors \(1,2,\ldots,k+1\), at least one is therefore not forbidden, and the greedy rule assigns \(v_i\) a color in this set.

It remains to check that the assignments form a proper coloring. If \(v_iv_j\) is an edge with \(i<j\), then \(v_i\) is already colored when \(v_j\) is processed. The color of \(v_i\) is forbidden at that step, so \(v_j\) receives a different color. This holds for every edge. Hence the procedure gives a proper coloring using at most \(k+1\) colors. \(\square\)

This proposition isolates the counting argument: at a given step, the relevant neighbors are the earlier ones, not all neighbors. The maximum degree gives a bound that works without knowing anything special about the order.

Proof. Fix any order of the vertices. Each vertex has at most \(\Delta(G)\) neighbors altogether, so it has at most \(\Delta(G)\) earlier neighbors. Thus the value \(k\) in the proposition satisfies \(k\leq\Delta(G)\). The proposition gives a proper greedy coloring using at most \(k+1\leq\Delta(G)+1\) colors. Since \(\chi(G)\) is the minimum number of colors in a proper coloring, it too is at most \(\Delta(G)+1\). No connectedness assumption is needed: the argument checks every vertex and every edge, including those in different components. \(\square\)

The theorem is an upper bound, not a claim that every vertex has \(\Delta(G)\) forbidden colors, or that the algorithm must use \(\Delta(G)+1\) colors. A vertex can have fewer than \(\Delta(G)\) earlier neighbors; even when it has many, some may have the same color. The next examples make these counts explicit.

Tracing the Bound

Why the Counting Argument Works

At the step for a vertex \(v\), write \(S(v)\) for its earlier neighbors and \(F(v)\) for the set of their colors. The precise count is

The first inequality allows different earlier neighbors to share a color. The second holds because earlier neighbors are only some of all the neighbors of \(v\). The third is the definition of maximum degree. Consequently, among \(\Delta(G)+1\) available colors, at least one is not in \(F(v)\). This is the complete reason the greedy choice can be made within the palette.

The argument also explains the role of the hypotheses. The graph is finite, so its vertices can be processed in a finite order, and for a nonempty graph its maximum degree is defined. No assumption that the graph is connected is needed. If a nonempty graph has \(\Delta(G)=0\), it has no edges: every vertex has degree 0. Greedy coloring then gives every vertex color 1, which is a proper coloring using \(0+1=1\) color. If the graph has no vertices, there are no steps and the empty assignment is a proper coloring; the stated theorem is restricted to nonempty graphs because \(\Delta(G)\) is not defined for that graph under the usual convention.

Common Mistake

Mistake: Counting neighbors instead of distinct forbidden colors and concluding that the center in the star example needs five colors because it has four neighbors. That calculation treats the four leaf colors as four different colors. But the traced algorithm assigns each leaf color 1, so the center’s forbidden set is \(\{1\}\), not a set of four colors. The center receives color 2. In general, the valid bound is that the number of forbidden colors is at most the number of earlier neighbors; it need not equal that number or the full degree.

Another error is to argue that the vertex has at most \(\Delta(G)\) forbidden colors without identifying which vertices can forbid them. The relevant set is the set of already colored neighbors. Later neighbors have not yet received colors, so they cannot forbid anything at the current step. Once this is stated, the count is immediate and applies at every position in every order.