Graph TheoryHardGraph Coloring
Graph Coloring · Hard problem
A wheel graph has a central hub vertex directly joined to all five vertices of a pentagon rim, where the rim vertices themselves form the cycle ( vertices, 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 exceed the TRUE chromatic number of this wheel?