pith. sign in

arxiv: 1102.0805 · v1 · pith:EQEW2ZQVnew · submitted 2011-02-03 · 💻 cs.DM · cs.DS· math.CO

Asymptotics of the chromatic number for quasi-line graphs

classification 💻 cs.DM cs.DSmath.CO
keywords chromaticgraphsnumberquasi-linegraphlineachievesagree
0
0 comments X
read the original abstract

As proved by Kahn, the chromatic number and fractional chromatic number of a line graph agree asymptotically. That is, for any line graph $G$ we have $\chi(G) \leq (1+o(1))\chi_f(G)$. We extend this result to quasi-line graphs, an important subclass of claw-free graphs. Furthermore we prove that we can construct a colouring that achieves this bound in polynomial time, giving us an asymptotic approximation algorithm for the chromatic number of quasi-line graphs.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.