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-colorin...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Bonomo, F., Chudnovsky, M., Maceli, P., Schaudt, O., Stein, M., Zhong, M.
Formato: JOUR
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_02099683_v38_n4_p779_Bonomo
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

Ejemplares similares

Ejemplares similares