Premium
Asymptotics of the Chromatic Number for Quasi‐Line Graphs
Author(s) -
King Andrew D.,
Reed Bruce
Publication year - 2013
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21679
Subject(s) - mathematics , combinatorics , chromatic scale , critical graph , discrete mathematics , graph coloring , line graph , chordal graph , chromatic polynomial , edge coloring , graph , graph power
Abstract 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 coloring that achieves this bound in polynomial time, giving us an asymptotic approximation algorithm for the chromatic number of quasi‐line graphs