Skip to main content

Research Repository

Advanced Search

Coloring graphs without short cycles and long induced paths

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

Authors

P. A. Golovach

J. Song



Contributors

O. Owe
Editor

M. Steffen
Editor

J. A. Telle
Editor

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). Coloring graphs without short cycles and long induced paths. In O. Owe, M. Steffen, & J. A. Telle (Eds.), Fundamentals of computation theory, 18th International Symposium (FCT 2011), 22-25 August 2011, Oslo, Norway ; proceedings (193-204). https://doi.org/10.1007/978-3-642-22953-4_17

Conference Name Fundamentals of Computation Theory, 18th International Symposium, FCT 2011
Conference Location Oslo, Norway
Publication Date Jan 1, 2011
Deposit Date Dec 6, 2011
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