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

  • $\begingroup$ Thank you Johan, this appears indeed a counterexample :) $\endgroup$ – 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).

  • $\begingroup$ 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? $\endgroup$ – joro Jun 17 '14 at 17:19
  • $\begingroup$ 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. $\endgroup$ – Dietrich Burde Jun 17 '14 at 18:08
  • $\begingroup$ 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? $\endgroup$ – joro Jun 18 '14 at 7:26
  • $\begingroup$ I see. This "index" is the fractional edge chromatic number, which is given by the fractional chromatic number of the associated line graph, right ? $\endgroup$ – Dietrich Burde Jun 18 '14 at 7:53
  • $\begingroup$ 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). $\endgroup$ – joro Jun 18 '14 at 8:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.