7
$\begingroup$

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.

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you Johan, this appears indeed a counterexample :) $\endgroup$
    – joro
    Commented Jun 20, 2014 at 9:44
8
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • $\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
    Commented Jun 17, 2014 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
    Commented Jun 17, 2014 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
    Commented Jun 18, 2014 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
    Commented Jun 18, 2014 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
    Commented Jun 18, 2014 at 8:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .