A Complexity Dichotomy for the Coloring of Sparse Graphs. Issue 1 (26th June 2012)

• Record Type: Journal Article
• Authors: Esperet, Louis; Montassier, Mickaël; Ochem, Pascal; Pinlou, Alexandre
• Is Part Of: Journal of graph theory. Volume 73:Issue 1(2013)
• Page Start: 85
• Page End: 102
• Publication Date: 2012-06-26
• Subjects: Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21659
• Languages: English
• ISSNs: 0364-9024

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>Galluccio, Goddyn, and Hell proved in 2001 that in any minor‐closed class of graphs, graphs with large enough girth have a homomorphism to any given odd cycle. In this paper, we study the computational aspects of this problem. Let <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9q59p2" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21659:equation:jgt21659-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="script">F</mml:mi></mml:math> be a monotone class of graphs containing all planar graphs, and closed under clique‐sum of order at most two. Examples of such class include minor‐closed classes containing all planar graphs, and such that all minimal obstructions are 3‐connected. We prove that for any <italic>k</italic> and <italic>g</italic>, either every graph of girth at least <italic>g</italic> in <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9q59qm" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21659:equation:jgt21659-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="script">F</mml:mi></mml:math> has a homomorphism to <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9q59r5" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21659:equation:jgt21659-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>C</mml:mi><mml:mrow><mml:mn>2</mml:mn><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub></mml:math>, or deciding whether a graph of girth <italic>g</italic> in <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9q59sq" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21659:equation:jgt21659-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="script">F</mml:mi></mml:math> has a homomorphism to <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9q59t8" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21659:equation:jgt21659-math-0005" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>C</mml:mi><mml:mrow><mml:mn>2</mml:mn><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub></mml:math> is NP‐complete. We also show that the same dichotomy occurs when considering 3‐Colorability or acyclic 3‐Colorability of graphs under various notions of density that are related to a question of Havel (On a conjecture of Grünbaum, J Combin Theory Ser B 7 (1969), 184–186) and a conjecture of Steinberg (The state of the three color problem, Quo Vadis, Graph theory?, Ann Discrete Math 55 (1993), 211–248) about the 3‐Colorability of sparse planar graphs.</p> </abstract>