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

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 '14 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 '14 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. – Dietrich Burde Jun 17 '14 at 18:08
• Sorry, but I am asking about EDGE coloring (chromatic INDEX) and you answer about VERTEX coloring (chromatic NUMBER). Assume G is claw-free (will edit). Would you please explain about EDGE coloring? – joro Jun 18 '14 at 7:26
• I see. This "index" is the fractional edge chromatic number, which is given by the fractional chromatic number of the associated line graph, right ? – Dietrich Burde Jun 18 '14 at 7:53
• Yes. The fractional chromatic number of the line graph L(G) is equal the fractional chromatic index of G, so line graph might help. Again, assume G is perfect claw free graph (will edit). – joro Jun 18 '14 at 8:00