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.

Improve this question
$\endgroup$
2
  • $\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, 2014 at 11:39
  • $\begingroup$ MO question about perfect graphs: mathoverflow.net/questions/172032/… $\endgroup$
    – joro
    Jun 17, 2014 at 13:45

1 Answer 1

Reset to default
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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