5
$\begingroup$

Brooks' Theorem says that

If $G$ is any connected graph that's neither complete nor an odd cycle, then $\chi(G) \leq \Delta(G)$

(Where $\chi$ is the colouring number and $\Delta(G)$ is the maximum degree of $G$.)

Why is this an important result? If you just colour $G$ using the greedy algorithm (colour each vertex with the first available colour), you get a colouring using at most $\Delta(G) + 1$ colours. Brooks' Theorem only improves on this by one, so what's the big deal?

$\endgroup$
3
  • 2
    $\begingroup$ Improving something by $1$ can be a big deal if that's the sort of thing you are interested in. You could ask the same question about the four-color theorem. $\endgroup$ Commented Sep 27, 2019 at 0:45
  • 1
    $\begingroup$ In sports it's considered a big deal when somebody breaks a record by a hundredth of a second. Why wouldn't lowering the upper bound for $\chi(G)$ by one whole colour be a huge deal? $\endgroup$
    – bof
    Commented Sep 27, 2019 at 8:14
  • $\begingroup$ You can look at things the other way around. Brooks theorem states that $\chi \le \Delta$. And, cool thing, a simple greedy algorithm almost achieves this bound. $\endgroup$
    – Kuifje
    Commented Sep 27, 2019 at 12:42

2 Answers 2

11
$\begingroup$

For small $\Delta$, Brooks's theorem is very strong. For example, it means that almost all $3$-regular graphs have chromatic number $3$: only those with a $K_4$ component can have chromatic number $4$, only the bipartite ones can have chromatic number $2$, and both of these are rare.

For large $\Delta$, Brooks's theorem is primarily interesting not because it's a particularly useful thing to say, but because it is often the best thing we can say. (The big deal is that we can't do better.) There are some results, and more conjectures, about strengthenings of Brooks's theorem:

  • When can we guarantee that $\Delta-1$ colors are enough? Clearly we need to assume the graph is $K_\Delta$-free. For large $\Delta$, this is enough; it's conjectured that this is enough for $\Delta \ge 9$.

  • When is it easy to test if a graph is $(\Delta+1-k)$-colorable? There is a polynomial-time algorithm if $k^2 + k \le \Delta$ (so for about $\Delta - \sqrt{\Delta}$ colors) and the problem is NP-complete if $k^2 + k > \Delta$.

For more details of these, the paper Brooks' theorem and beyond by Cranston and Rabern is a good source.

$\endgroup$
0
$\begingroup$

Finding reduced upper bounds for $\chi (G)$ by applying Brooks’ theorem iteratively

If you are looking to improve on the upper bound of $\chi(G)≤\Delta(G)+1$ for a specific graph $G$ there is a solution that relies on Brook’s theorem.

Brooks’ theorem can be applied iteratively in a “divide-and-conquer” strategy (as illustrated below) to improve the upper bound of $\chi(G)$. Note that Brooks’ theorem deals with the two exception cases separately:

  • for $\Delta(G) = 2$, it needs to consider the possibility of odd-cycles in graph $G$
  • for $\Delta(G)≥ 2$, where it needs to consider the possibility that graph $G$ contains a $(\Delta(G)+1)$-clique

The procedure below does this too.

The main idea is that we start by assuming a certain $\chi (G) ≤ \Delta(G)$ it is possible to remove “redundant” vertices (and their associated edges) and thus reduce the associated degree of the remaining neighboring vertices in the reduced graph. By doing this incrementally (and with it creating ever more reduced graphs it is possible (depending on the structure of the original graph) to reach a reduced upper bound. Illustrative procedure as follows:

Let's start by taking the original graph $G$ and number this $G_1$.

First round of iteration:

  • Choose $k = 2$ and assume $\chi (G_1) ≥ k$. This means that any vertex with a degree of one is redundant. Such a vertex is at the end of a branch and thus it is colorable if the one vertex adjacent is colorable, and it is thus not critical. Remove this vertex and continue to remove vertices until there are no further vertices with a degree of one. If this results in the removal of all vertices, the original graph $G$ is a tree and thus $\chi (G_1) = 2$. If not, this results in a reduced graph $G_2$ where the minimum degree of all vertices is two (NB : graph $G_2$ does not have any branches and thus consists of cyclic subgraphs).
  • Now, with the reduction in vertices (and thus fewer edges), $2≤\chi(G_k)≤ \Delta(G_k)+1$. Continue to the next round of iteration (see below), unless in the specific case of $\Delta(G_2)=2$; if so, the graph $G_2$ is 2-regular and $2 ≤ \chi(G_2) ≤ 3$; graph $G_2$ may contain an odd-cycle. This is only the case iff the graph $G_k$ is not bipartite, resulting in $\chi(G_1)=\chi(G_2)=3$, otherwise $\chi(G_1)=\chi(G_2)= 2$. Whether graph $G_2$ is bipartite can be tested by established DFS or BFS algorithms with time complexity $O(|V|^2)$. No further rounds of iteration are needed.

Next round of iteration:

  • Increase $k$ by one and assume $\chi(G_{k-1}) ≥ k$. This means that any vertex of graph $G_{k-1}$ with degree $(k-1)$ is redundant (e.g. for the case $k=3$, a vertex with degree two sits between only two other vertices, and iff these two are colorable, the middle vertex is colorable and is thus not critical so can be removed. Similarly, this principle applies to higher orders of $k$).

  • Again, continue to remove vertices until there are no vertices left with degree of $(k-1)$. If this results in the removal of all vertices, the upper bound is limited to $\chi(G_{k-1}) ≤ k$. If not, the result is a reduced graph $G_k$ where the minimum degree of all vertices is $k$.

  • If the maximum degree $\Delta(G_k) = k$, then the graph $G_k$ is $k$-regular, and we check for the existence of a $(k+1)$-clique in $G_k$. If this is the case $\chi(G_1) = (k+1)$; if this not the case, the upper bound $\chi(G_k)$ for reduced graph $G_k$ is set at $\chi(G_k) ≤ k$. (NB: time complexity for finding a $k$-clique in a $k$-regular (potentially disconnected), graph is $O(|V|^{k+1})$ ; this is polynomial, but still practically intractable for large $k$, so if this is a practical limitation you can skip this test and instead assume $\chi(G_k) ≤ k+1$).

  • If graph $G_k$ is not $k$-regular (i.e. $k<\Delta(G_k)$), repeat with the next round of iteration.

End of procedure:

  • Ultimately, the above rounds of iterations must end for some $k ≤ \Delta(G_1)$. For this $k$ either all vertices are removed, or the reduced graph $G_k$ becomes $k$-regular.
  • Because in each iteration we only removed redundant vertices, it means that $\chi(G_{k-1}) ≤ \chi(G_k)$. So, by induction, it means that the upper bound for $\chi(G_1)$ can be reduced to $\chi(G_1) ≤ k$, or in the case of the reduced graph $G_k$ ending up being $k$-regular and containing a $(k+1)$-clique, $\chi(G_1) = (k+1)$.

Graph with known clique number:

  • For the clique number $\omega(G)$ (i.e. the size of largest clique subgraph of $G$), $\chi(G) ≥ \omega(G)$.
  • If $\omega(G)$ is known, one can start the above procedure with $k = \omega(G)$, and start by removing vertices with degree smaller than $k$.

In short:

  • by iteratively applying Brooks' theorem, it is possible to improve on the upper bound of $\chi(G) ≤ \Delta(G)+1$ for a wide range of graphs. In certain cases it is even possible to determine $\chi(G)$ in polynomial time (may still be impractically long).
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .