Talk:Brooks' theorem

Hello, I don't understand why my contribution has been removed. In the page on Grötzsch's theorem it is stated clearly (my own contribution) that a planar graph not containing K_4 and still not 4-colorable exists. Since an example (not found by me) is available, namely http://math.asu.edu/~checkman/steinberg5cycle.jpg, i do not understand what exactly is disputable here. Delio.mugnolo (talk) 09:35, 31 December 2010 (UTC)

What does this have to do with graphs of maximum degree Δ? Your example has no K_4, but its maximum degree is 5? In any case a much simpler counterexample to the removed statement (for small Δ) is possible: the pentagonal prism has Δ=3, is triangle-free, but requires three colors instead of only two. —David Eppstein (talk) 17:59, 31 December 2010 (UTC)

Sorry, you are right. —Delio.mugnolo (talk) 14:11, 1 January 2011 (UTC)

List colouring

The article claims, without a reference (it’s not in Lovász’s paper!) that “A small modification of the proof of Lovász applies to this case: ...”. The given argument for 2-connected Δ-regular graphs indeed works as described. But I don’t see how to deal with graphs that are not 2-connected. In the case of ordinary Δ-colouring, this is straightforward: colour each 2-connected block separately, and then combine them by attaching one block at a time; crucially, we can permute the colours in the block such that the colour of the cut vertex where it is being attached agrees with the already constructed part of the colouring. But one cannot do such kind of permutation with list colouring.—Emil J. 11:10, 18 October 2024 (UTC)

Hmm. I guess the following proof works, though it is not a “modification of the proof of Lovász”; rather, it shows that Brooks’s theorem for ordinary colouring, as a black box, implies Brooks’s theorem for list colouring.

Let G be a connected graph of maximal degree Δ that satisfies the assumptions of the theorem, and L an assignment of lists of size Δ to all vertices. If L is constant, this is an ordinary Δ-colouring, hence L has a choice function by the ordinary Brooks’s theorem.

Otherwise, let B₀, ..., B_t be a listing of all 2-connected blocks of G such that B₀ ∪ ... ∪ B_i is connected for each i ≤ t, i.e., B_i is a leaf block of B₀ ∪ ... ∪ B_i. Since L is not constant, and G is connected, L is nonconstant on some edge, and therefore on some B_s. Let s be maximal such. By assumption, B_s is a leaf block of B₀ ∪ ... ∪ B_s, thus it contains only one cut vertex x of B₀ ∪ ... ∪ B_s. Consequently, B_s contains two adjacent vertices u and v such that L(u) ≠ L(v) and u is not a cut vertex, thus we can construct a spanning tree of B₀ ∪ ... ∪ B_s with root v and leaf u. We give u a color not available to v, and proceed up the tree to colour the remaining vertices; we can colour v in the end as only Δ − 1 of its neighbours can have a conflicting colour. Thus, there is a colouring of B₀ ∪ ... ∪ B_s consistent with L.

By induction on i = s, ..., t, we extend it to a colouring of B₀ ∪ ... ∪ B_i as follows: if we have already coloured B₀ ∪ ... ∪ B_i, then B_i+1 is a leaf block of B₀ ∪ ... ∪ B_i+1 with a cut vertex x. Since L is constant on B_i+1, ordinary Brooks’s theorem gives a colouring of B_i+1. (Actually, since x has neighbours in B₀ ∪ ... ∪ B_i, it has degree ≤ Δ − 1 in B_i+1; thus, we can just colour B_i+1 using a spanning tree with root x.) Then we can permute the colours so that the colour of x agrees with the already constructed colouring of B₀ ∪ ... ∪ B_i, thus we get a colouring of B₀ ∪ ... ∪ B_i+1.—Emil J. 15:57, 18 October 2024 (UTC)

There is a proof in hdl:1721.1/112878 (Corollary 3.4) but despite referencing Lovasz and using the idea of farthest-distance-first coloring the proof is not merely a small modification of Lovasz's proof. I removed the unsourced claim that this can be proven as a small modification. —David Eppstein (talk) 18:15, 18 October 2024 (UTC)

All right, thank you.

For the record, I realized I was making the proof too complicated; the induction argument is not needed. I will prove below that if G is a connected graph of maximum degree ≤ Δ, and L is an assignment of lists of size Δ to vertices, then G has an L-colouring unless G is 2-connected and Δ-regular, and L is constant on G. I’m assuming Δ ≥ 2 to avoid funny exceptions (for Δ = 0, K₁ has 0 2-connected blocks; for Δ = 1, K₂ has exactly one 2-connected block, but it is denied the title of being 2-connected by the big boys). We distinguish a few cases:

If G has a vertex v of degree < Δ, we can colour it using a spanning tree with root v.

If G has two adjacent vertices u and v such that L(u) ≠ L(v) and G − {u} is connected, we can colour it using a spanning tree with root v and leaf u attached to the root; we start by giving u a colour not available to v. In particular, this applies whenever G is 2-connected and L is not constant on G.

If L is not 2-connected, let B be a leaf block of G with cut vertex x, and B’ the union of the remaining blocks of G, so that B ∩ B’ = {x}. If L is not constant on B, there are adjacent u and v in B such that L(u) ≠ L(v), and we may assume u ≠ x, thus u is not a cut vertex, i.e., G − {u} is connected, thus G can be coloured by the previous paragraph. Otherwise, the degrees of x in B and in B’ are < Δ as it has neighbours in both, thus we can colour B and B’ separately; since L is constant on B, we can permute the colouring of B so that the colour of x agrees with its colour in B’, thus we can combine them to a colouring of G.—Emil J. 09:07, 19 October 2024 (UTC)