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
Autor principal: Bonomo, Flavia
Publicado: 2018
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_02099683_v38_n4_p779_Bonomo
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
id paper:paper_02099683_v38_n4_p779_Bonomo
record_format dspace
spelling paper:paper_02099683_v38_n4_p779_Bonomo2023-06-08T15:20:40Z Three-Coloring and List Three-Coloring of Graphs Without Induced Paths on Seven Vertices Bonomo, Flavia 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. © 2018, János Bolyai Mathematical Society and Springer-Verlag GmbH Germany, part of Springer Nature. Fil:Bonomo, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2018 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_02099683_v38_n4_p779_Bonomo http://hdl.handle.net/20.500.12110/paper_02099683_v38_n4_p779_Bonomo
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
description 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. © 2018, János Bolyai Mathematical Society and Springer-Verlag GmbH Germany, part of Springer Nature.
author Bonomo, Flavia
spellingShingle Bonomo, Flavia
Three-Coloring and List Three-Coloring of Graphs Without Induced Paths on Seven Vertices
author_facet Bonomo, Flavia
author_sort Bonomo, Flavia
title Three-Coloring and List Three-Coloring of Graphs Without Induced Paths on Seven Vertices
title_short Three-Coloring and List Three-Coloring of Graphs Without Induced Paths on Seven Vertices
title_full Three-Coloring and List Three-Coloring of Graphs Without Induced Paths on Seven Vertices
title_fullStr Three-Coloring and List Three-Coloring of Graphs Without Induced Paths on Seven Vertices
title_full_unstemmed Three-Coloring and List Three-Coloring of Graphs Without Induced Paths on Seven Vertices
title_sort three-coloring and list three-coloring of graphs without induced paths on seven vertices
publishDate 2018
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_02099683_v38_n4_p779_Bonomo
http://hdl.handle.net/20.500.12110/paper_02099683_v38_n4_p779_Bonomo
work_keys_str_mv AT bonomoflavia threecoloringandlistthreecoloringofgraphswithoutinducedpathsonsevenvertices
_version_ 1768543366898778112

Ejemplares similares