• 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