INVESTIGADORES
BONOMO flavia
artículos
Título:
Three-coloring and list three-coloring of graphs without induced paths on seven vertices
Autor/es:
BONOMO, FLAVIA; CHUDNOVSKY, MARIA; MACELI, PETER; SCHAUDT, OLIVER; STEIN, MAYA; ZHONG, MINGXIAN
Revista:
COMBINATORICA
Editorial:
SPRINGER
Referencias:
Lugar: Berlin; Año: 2018 vol. 38 p. 779 - 801
ISSN:
0209-9683
Resumen:
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.
