Skip to main content
2 of 2
Two relaxations and clarification about edge coloring
joro
  • 25.4k
  • 10
  • 66
  • 121

Conjecture: for perfect graphs the fractional chromatic index rounded up equals the chromatic index

Let $\chi'_f(G)$ be the fractional chromatic index.

Based on limited experiments (up to 8 vertices and few larger graphs), I suspect:

Conjecture For perfect graphs $\lceil \chi'_f(G) \rceil = \chi'(G)$

Conjecture 2 (new) For cubic claw-free perfect graphs $\lceil \chi'_f(G) \rceil = \chi'(G)$

Conjecture 3 (new) For claw-free perfect graphs $\lceil \chi'_f(G) \rceil = \chi'(G)$

Sage's fractional_chromatic_index() is not efficient for me, is there another implementation?

Counterexamples or proof (especially of (2)) are welcome.

Observe that the question is about edge coloring, not for vertex coloring.

joro
  • 25.4k
  • 10
  • 66
  • 121