@article{319c1f1068d545369375c081555368db,
title = "Three-Coloring and List Three-Coloring of Graphs Without Induced Paths on Seven Vertices",
abstract = "In this paper we present a polynomial time algorithm that determines if an input graph containing no induced seven-vertex path is 3-colorable. This affirmatively answers a question posed by Randerath, Schiermeyer and Tewes in 2002. Our algorithm also solves the list-coloring version of the 3-coloring problem, where every vertex is assigned a list of colors that is a subset of {1,2,3}, and gives an explicit coloring if one exists.",
author = "Flavia Bonomo and Maria Chudnovsky and Peter Maceli and Oliver Schaudt and Maya Steinz and Mingxian Zhong",
note = "Funding Information: ∗Partially supported by MathAmSud Project 13MATH-07, UBACyT Grant 20020130100808BA, CONICET PIP 112-201201-00450CO and ANPCyT PICT 2012-1324. † Partially supported by NSF grants IIS-1117631, DMS-1001091 and DMS-1265803. ‡Partially supported by MathAmSud Project 13MATH-07, Fondecyt grant 1140766, and Millenium Nucleus Information and Coordination in Networks. Publisher Copyright: {\textcopyright} 2018, J{\'a}nos Bolyai Mathematical Society and Springer-Verlag GmbH Germany, part of Springer Nature.",
year = "2018",
month = aug,
day = "1",
doi = "10.1007/s00493-017-3553-8",
language = "English (US)",
volume = "38",
pages = "779--801",
journal = "Combinatorica",
issn = "0209-9683",
publisher = "Janos Bolyai Mathematical Society",
number = "4",
}