Asymptotics of the chromatic number for quasi-line graphs
2013
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 colouring that achieves this bound in polynomial time, giving us an asymptotic approximation algorithm for the chromatic number of quasi-line graphs.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
27
References
6
Citations
NaN
KQI