@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.",

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",

}