Skip to main content
Post Made Community Wiki
Source Link
Andrew D. King
  • 1.8k
  • 2
  • 17
  • 18

If you're going to be completely honest about the question, you need to consider edge colourings of multigraphs. Even in this case there are not a lot of open problems. Vizing's theorem already tells us that the chromatic index differs from the maximum degree by at most the maximum multiplicity. However, more is known:

  • We can compute the fractional chromatic index in polynomial time; even approximating the fractional chromatic number of a graph is hard.

  • The fractional chromatic index and the chromatic index agree asymptotically, as first proven by Kahn. However, the chromatic number is not even bounded by any function of the fractional chromatic number.

  • The Goldberg-Seymour conjecture implies that $\chi'_f$ and $\chi'$ differ by at most one. This is a long-standing open problem on the chromatic index. So what does that leave? Well, proving that the difference is bounded by some universal constant, but not too much else.