P. A. Golovach
Coloring graphs without short cycles and long induced paths
Golovach, P. A. ; Paulusma, D.; Song, J.
Authors
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 |
You might also like
Matching cuts in graphs of high girth and H-free graphs
(2023)
Conference Proceeding
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
An algorithmic framework for locally constrained homomorphisms
(2023)
Journal Article
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
Computing Subset Vertex Covers in H-Free Graphs
(2023)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search