Asymptotics of the Chromatic Number for Quasi‐Line Graphs. Issue 3 (5th July 2012) - King, Andrew D.; Reed, Bruce
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 <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1zv4tsfr" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />χ(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