Can I read Asymptotics of the Chromatic Number for Quasi-line Graphs on EtoBox?

Asymptotics of the Chromatic Number for Quasi-line Graphs by King, Andrew D.; Reed, Bruce is a scholarly article available to read on EtoBox.

What is Asymptotics of the Chromatic Number for Quasi-line Graphs about?

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.

Author

King, Andrew D.; Reed, Bruce

Published

2011

Language

EN