ICC 25427
INSTITUTO DE INVESTIGACION EN CIENCIAS DE LA COMPUTACION
Unidad Ejecutora - UE
artículos
Título:
Three-coloring and list three-coloring of graphs without induced paths on seven vertices
Autor/es:
BONOMO, FLAVIA; SCHAUDT, OLIVER; MACELI, PETER; ZHONG, MINGXIAN; CHUDNOVSKY, MARIA; STEIN, MAYA
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.
