MathCastle
Graph TheoryHardGraph Coloring

Graph Coloring · Hard problem

A wheel graph W5W_5 has a central hub vertex 00 directly joined to all five vertices 1,2,3,4,51,2,3,4,5 of a pentagon rim, where the rim vertices themselves form the cycle 1-2-3-4-5-11\text{-}2\text{-}3\text{-}4\text{-}5\text{-}1 (66 vertices, 1010 edges total). Brooks' theorem applies to this graph since it is connected, not complete, and not an odd cycle. By how much does Brooks' bound Δ(G)\Delta(G) exceed the TRUE chromatic number of this wheel?