Asymptotics of the Chromatic Number for Quasi‐Line Graphs. Issue 3 (5th July 2012) - King, Andrew D.
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 χ(G)≤(1+o(1))χ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 coloring that achieves this bound in polynomial time, giving us an asymptotic approximation algorithm for the chromatic number of quasi‐line graphs