Coloring graphs without short cycles and long induced paths

Golovach, P. A. ; Paulusma, D.; Song, J.

Abstract

The girth of a graph G is the length of a shortest cycle in G. For any fixed girth g ≥ 4 we determine a lower bound ℓ(g) such that every graph with girth at least g and with no induced path on ℓ(g) vertices is 3-colorable. In contrast, we show the existence of an integer ℓ such that testing for 4-colorability is NP-complete for graphs with girth 4 and with no induced path on ℓ vertices.

Citation

Golovach, P. A., Paulusma, D., & Song, J. (2011, December). Coloring graphs without short cycles and long induced paths. Presented at Fundamentals of Computation Theory, 18th International Symposium, FCT 2011, Oslo, Norway

• Presentation Conference Type: Conference Paper (published)
• Conference Name: Fundamentals of Computation Theory, 18th International Symposium, FCT 2011
• Publication Date: Jan 1, 2011
• Deposit Date: Dec 6, 2011
• Print ISSN: 0302-9743
• Pages: 193-204
• Series Title: Lecture notes in computer science
• Series Number: 6914
• Series ISSN: 0302-9743,1611-3349
• Book Title: Fundamentals of computation theory, 18th International Symposium (FCT 2011), 22-25 August 2011, Oslo, Norway ; proceedings.
• ISBN: 9783642229527
• DOI: https://doi.org/10.1007/978-3-642-22953-4_17
• Public URL: https://durham-repository.worktribe.com/output/1158685