Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4652944 | Electronic Notes in Discrete Mathematics | 2007 | 5 Pages |
Abstract
It was proved by Kahn [J. Kahn, Asymptotics of the chromatic index for multigraphs, Journal of Combinatorial Theory Series A 68 (1996) 233–254] that 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; G is a quasi-line graph if the neighbourhood of any vertex of G can be covered by two cliques.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics