@article{2f57f311590e4106b1bd83febca8260a,
title = "Approximately Coloring Graphs Without Long Induced Paths",
abstract = "It is an open problem whether the 3-coloring problem can be solved in polynomial time in the class of graphs that do not contain an induced path on t vertices, for fixed t. We propose an algorithm that, given a 3-colorable graph without an induced path on t vertices, computes a coloring with max{5,2⌈t-12⌉-2} many colors. If the input graph is triangle-free, we only need max{4,⌈t-12⌉+1} many colors. The running time of our algorithm is O((3 t-2+ t2) m+ n) if the input graph has n vertices and m edges.",
keywords = "Approximation algorithm, Forbidden induced paths, Graph coloring",
author = "Maria Chudnovsky and Oliver Schaudt and Sophie Spirkl and Maya Stein and Mingxian Zhong",
note = "Funding Information: The first author was supported by National Science Foundation grant DMS-1550991 and US Army Research Office Grant W911NF-16-1-0404. The fourth author was supported by Fondecyt Grants 1140766 and 1180830, by CMM-Basal AFB 170001, and by Millennium Nucleus Information and Coordination in Networks. Funding Information: We are thankful to Paul Seymour for many helpful discussions. We thank Stefan Hougardy for pointing out [20] to us. This material is based upon work supported in part by the U.S. Army Research Laboratory and the U.S. Army Research Office under Grant No. W911NF-16-1-0404. Funding Information: Acknowledgements We are thankful to Paul Seymour for many helpful discussions. We thank Stefan Hougardy for pointing out [20] to us. This material is based upon work supported in part by the U.S. Army Research Laboratory and the U.S. Army Research Office under Grant No. W911NF-16-1-0404. Publisher Copyright: {\textcopyright} 2019, Springer Science+Business Media, LLC, part of Springer Nature.",
year = "2019",
month = aug,
day = "1",
doi = "10.1007/s00453-019-00577-6",
language = "English (US)",
volume = "81",
pages = "3186--3199",
journal = "Algorithmica",
issn = "0178-4617",
publisher = "Springer New York",
number = "8",
}