Calculating A Chromatic Number
Basic Principles for Calculating Chromatic Numbers: Although the chromatic number is one of the most studied parameters in graph theory, no formula exists for the chromatic number of an arbitrary graph. Thus, for the most part, one must be content with supplying bounds for the chromatic number of graphs.
A few basic principles recur in many chromatic-number calculations. Now, we will try to find upper and lower bound to provide a direct approach to the chromatic number of a given graph.
Upper bound: Show (G) ≤ k by exhibiting a proper k-coloring of G.
Lower bound: Show (G) ≥ k by using properties of graph G, most especially, by finding a subgraph that requires k-colors.
Proposition 1. Let G be a graph with k-mutually adjacent vertices. Then (G) ≥ k.
Proof. Using fewer than k colors on graph G would result in a pair from the mutually adjacent set of k vertices being assigned the same color.
Proposition 2. Let H be a subgraph of G. Then (G) ≥ (H).
Proof. Whatever colors are used on the vertices of subgraph H in a minimum coloring of G can also be used in coloring of H by itself.
Corollary 1. Let G be a graph. Then (G) ≥ !(G).
Proof. Since clique is a subgraph of G, we get this inequality.
The 4-coloring of the graph G shown in Figure 3.2 establishes that (G) ≤ 4, and the K4-subgraph (drawn in bold) shows that (G) ≥ 4. Hence, (G) = 4.
Proposition 3. Let G be any graph. Then
Proof. Given a k-coloring of G, the vertices being colored with the same color form an independent set. Let G be a graph with n vertices and c a k-coloring of G. We define
Vi = {v | c(v) = i} for i = 0, 1, ..., k.
Each Vi is an independent set. Let (G) be the independence number of G, we have Vi ≤ (G). Since
n = |V (G)| = |V1| |V2| ... |Vk| ≤ k (G) = (G) (G)
we have
Most upper bounds on the chromatic number come from algorithms that produce colorings. For example, assigning distinct colors to the vertices yields (G) ≤ n(G). This bound is best possible, since (Kn) = n, but it holds with equality only for complete graphs. We can improve a “best possible” bound by obtaining another bound that is always at least as good. For example (G) ≤ n(G) uses nothing about the structure of G; we can do better by coloring the vertices in some order and always using the “least available” color.
Definition 1. The greedy coloring relative to a vertex ordering v1, v2, ..., vn of V (G) is obtained by coloring vertices in order v1, v2, ..., vn, assigning to vi the smallest-indexed color not already used on its lower-indexed neighbors.
Theorem . For any graph G,
(G) ≤ Δ(G) 1.
Proof. In a vertex ordering, each vertex has at most (G) earlier neighbors, so the greedy coloring cannot be forced to use more than Δ(G) 1 colors. This proves constructively that (G) ≤ Δ(G) 1.
The bound Δ(G) 1 is the worst upper bound that greedy coloring could produce. Choosing the vertex ordering carefully yields improvements. We can avoid the trouble caused by vertices of high degree by putting them at the beginning, where they won’t have many earlier neighbors.