2
$\begingroup$

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

For which graph classes $\lceil \chi'_f(G) \rceil = \chi'(G)$?

Since $\chi'_f(G)$ is computable in polynomial time, solving this gives tractable graph classes.

Experiments with Sage suggest this is true for perfect graphs on up to $8$ vertices, though Sage's implementation is not inefficient.

$\endgroup$
  • $\begingroup$ Sage is a free software. If you find a part of it too slow, come and write some code ! :-P $\endgroup$ – Nathann Cohen Jun 17 '14 at 11:39
  • $\begingroup$ MO question about perfect graphs: mathoverflow.net/questions/172032/… $\endgroup$ – joro Jun 17 '14 at 13:45
4
$\begingroup$

It is known that for any multigraph $G$ on at most 8 vertices, $\chi'(G)$ is the maximum of the maximum degree and the ceiling of the odd-sets bound, see http://dx.doi.org/10.1016/S0012-365X(96)00364-0 (so what you find with sage is not very surprising).

This recent arXiv manuscript gives some more references for your problem (top of page 3) http://arxiv.org/pdf/1406.0757v1.pdf

Beside bipartite graphs, non-trivial classes with the property you're looking for include series-parallel graphs.

$\endgroup$
  • $\begingroup$ Thank you. Is it known for perfect graphs? $\endgroup$ – joro Jun 17 '14 at 13:45
  • $\begingroup$ I tried larger graphs (24 vertices) in sage and it appears true too. $\endgroup$ – joro Jun 17 '14 at 13:48

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.