Skip to main content
Post Made Community Wiki by Emil
Source Link
Emil
  • 726
  • 4
  • 13

Why is edge-coloring less interesting than vertex-coloring?

I was wondering why there is (apparently) much more research directed towards vertex-coloring than edge-coloring? Prima facie, it seems that edge-coloring is just as "natural" a thing to investigate.

I can think of a few reasons:

  1. Vertex coloring is well behaved under deletion and contraction of edges.
  2. Vertex colorability is closely linked to the cycle matroid.
  3. Edge-coloring can be regarded as vertex-coloring restricted to line graphs.
  4. Since Vizing's theorem (that the chromatic index of $G$ is either $\Delta(G)$ or $\Delta(G)+1$) edge-coloring has been solved (asymptotically).

But is it really true that edge-coloring is less interesting than vertex-coloring?