Skip to main content
1 of 1
Post Made Community Wiki
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

I actually do think that vertex-colouring is more interesting than edge-colouring, although I fully admit that this is my own personal bias. Instead of focusing on why edge-colouring is uninteresting, let me highlight why I think vertex-colouring is interesting.

Connections to topology. Along these lines there is of course the 4-colour theorem, Heawood's map conjecture, and Grötzsch's theorem. For planar graphs there is also a suitable notion of duality of colourings via flow-colouring duality. Kristal's answer is an instance of flow-colouring duality in action. That is, it suffices to prove the 4-colour theorem for planar triangulations. The dual of a planar triangulation is a cubic planar graph. So, it suffices to show that cubic planar graphs have 4-flows, and it's sort of an accident that 4-flows for cubic graphs actually correspond to 3-edge colourings.

Structural graph theory. Perhaps the most famous open problem in graph theory is Hadwiger's Conjecture, which connects vertex colouring to clique-minors. So, high chromatic number can actually force some structure, while high edge-chromatic number just forces high maximum degree.

Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187