Asymptotics of the Chromatic Number for Quasi‐Line Graphs. Issue 3 (5th July 2012)

• Record Type: Journal Article
• Authors: King, Andrew D.; Reed, Bruce
• Is Part Of: Journal of graph theory. Volume 73:Issue 3(2013)
• Page Start: 327
• Page End: 341
• Publication Date: 2012-07-05
• Subjects: Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21679
• Languages: English
• ISSNs: 0364-9024

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>As proved by Kahn, the chromatic number and fractional chromatic number of a line graph agree asymptotically.That is, for any line graph <italic>G</italic>, we have <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1zv4tsfr" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21679:jgt21679-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>χ</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mo>≤</mml:mo><mml:mrow><mml:mo>(</mml:mo><mml:mn>1</mml:mn><mml:mo>+</mml:mo><mml:mi>o</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mn>1</mml:mn><mml:mo>)</mml:mo></mml:mrow><mml:mo>)</mml:mo></mml:mrow><mml:msub><mml:mi>χ</mml:mi><mml:mi>f</mml:mi></mml:msub><mml:mrow><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math>. 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</p> </abstract>