Asymptotics of the Chromatic Number for Quasi-Line Graphs

作者：King Andrew D^*; Reed Bruce

来源：Journal of Graph Theory, 2013, 73(3): 327-341.

DOI：10.1002/jgt.21679

• graph coloring
• fractional graph coloring
• quasi-line graph
• chromatic number
• approximation algorithm

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

• 出版日期2013-7