info:eu-repo/semantics/article
Three-coloring and list three-coloring of graphs without induced paths on seven vertices
Date
2018-08Registration in:
Bonomo, Flavia; Chudnovsky, Mariana; Maceli, Peter; Schaudt, Oliver; Stein, Maya; et al.; Three-coloring and list three-coloring of graphs without induced paths on seven vertices; Springer; Combinatorica; 38; 4; 8-2018; 779-801
0209-9683
CONICET Digital
CONICET
Author
Bonomo, Flavia
Chudnovsky, Mariana
Maceli, Peter
Schaudt, Oliver
Stein, Maya
Zhong, Mingxian
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.