Three-coloring and list three-coloring of graphs without induced paths on seven vertices

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.Fil: Bonomo, Flavia. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigación en Ciencias de la Computación; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; ArgentinaFil: Chudnovsky, Mariana. University of Princeton; Estados UnidosFil: Maceli, Peter. Canisius College; Estados UnidosFil: Schaudt, Oliver. Universitat zu Köln; AlemaniaFil: Stein, Maya. Universidad de Chile; ChileFil: Zhong, Mingxian. Columbia University; Estados Unido