Title of article :
Asymptotics of the chromatic number for quasi-line graphs
Author/Authors :
King، نويسنده , , Andrew D. and Reed، نويسنده , , Bruce، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2007
Pages :
5
From page :
327
To page :
331
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.
Keywords :
Quasi-line graph , fractional chromatic number , Chromatic index , chromatic number
Journal title :
Electronic Notes in Discrete Mathematics
Serial Year :
2007
Journal title :
Electronic Notes in Discrete Mathematics
Record number :
1454735
Link To Document :
بازگشت