Title: Asymptotics of the Chromatic Number for Quasi‐Line Graphs
Abstract: 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 . 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