# 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.

• Related question on cstheory SE at cstheory.stackexchange.com/questions/24915 For which graph classes the fractional chromatic index rounded up equals the chromatic index? Jun 18, 2014 at 9:35

A result of Cai and Ellis (see Theorem 5 in http://www.sciencedirect.com/science/article/pii/0166218X9190010T) implies that deciding whether a cubic perfect line-graph is $3$-edge-colorable is NP-complete. Counter-examples to Conjecture 2 can be built from their argument as follows:

First, notice that every cubic bridgeless graph $G$ satisfies $\chi_f'(G)=3$. This is easily obtained using the following formula for $\chi_f'(G)$, which is derived from Edmonds' inequalities for the matching polytope of $G$: $$\chi_f'(G)=\max\left(\Delta(G),\max_{U\subseteq V(G), |U|\geq 3\, \text{odd}}\frac{|E(U)|}{\frac{|U|-1}{2}}\right).$$

Now, consider the following construction: let $H$ be a bridgeless cubic graph and $S(H)$ be the graph obtained from $H$ by subdividing each edge exactly once. Let $G$ be the line graph of $S(H)$.

It is straightforward to check that $G$ is cubic, bridgeless and that: $\chi'(G)=3$ if and only if $\chi'(H)=3$. Furthermore, $G$ is perfect because $S(H)$ is bipartite.

Therefore, if $H$ is a cubic bridgeless graph with $\chi'(H)=4$ (for example the Petersen graph or any other snark http://en.wikipedia.org/wiki/Snark_(graph_theory)), then $G$ is a cubic bridgeless perfect line-graph with $\chi'(G)>\lceil\chi_f'(G)\rceil$.

• Thank you Johan, this appears indeed a counterexample :)
– joro
Jun 20, 2014 at 9:44

It is shown in "On claw-free t-perfect graphs" by Bruhn and Stein that indeed $\lceil \chi'_f(G) \rceil = \chi'(G)$ holds for claw-free $h$-perfect graphs, see corollary $16$. This also holds for $h$-perfect line-graphs and $t$-perfect claw-free graphs, see the paper of Benchetrit, Theorem $3$ and Theorem $4$. However, Benchetrit says that it does not hold for $h$-perfect graphs in general (see the remark with references after Theorem $4$). So there are counterexamples (by Laurent and Seymour in 2003).

• What is the exact reference for the counterexample (the paper shows counterexample about vertex coloring). And except for sharing the name "perfect" why their results apply to perfect graphs?
– joro
Jun 17, 2014 at 17:19
• Perfect graphs are also $h$-perfect. To the first question - $t$-perfetc graphs with the integer round-up property must have chromatic number at most $3$. The examples of Laurent and Seymour are t-perfect graphs which are not 3-colorable. Jun 17, 2014 at 18:08