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...
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | JOUR |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_02099683_v38_n4_p779_Bonomo |
| Aporte de: |
| id |
todo:paper_02099683_v38_n4_p779_Bonomo |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_02099683_v38_n4_p779_Bonomo2023-10-03T15:09:58Z Three-Coloring and List Three-Coloring of Graphs Without Induced Paths on Seven Vertices Bonomo, F. Chudnovsky, M. Maceli, P. Schaudt, O. Stein, M. Zhong, M. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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. |
| format |
JOUR |
| author |
Bonomo, F. Chudnovsky, M. Maceli, P. Schaudt, O. Stein, M. Zhong, M. |
| spellingShingle |
Bonomo, F. Chudnovsky, M. Maceli, P. Schaudt, O. Stein, M. Zhong, M. Three-Coloring and List Three-Coloring of Graphs Without Induced Paths on Seven Vertices |
| author_facet |
Bonomo, F. Chudnovsky, M. Maceli, P. Schaudt, O. Stein, M. Zhong, M. |
| author_sort |
Bonomo, F. |
| 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 |
| url |
http://hdl.handle.net/20.500.12110/paper_02099683_v38_n4_p779_Bonomo |
| work_keys_str_mv |
AT bonomof threecoloringandlistthreecoloringofgraphswithoutinducedpathsonsevenvertices AT chudnovskym threecoloringandlistthreecoloringofgraphswithoutinducedpathsonsevenvertices AT macelip threecoloringandlistthreecoloringofgraphswithoutinducedpathsonsevenvertices AT schaudto threecoloringandlistthreecoloringofgraphswithoutinducedpathsonsevenvertices AT steinm threecoloringandlistthreecoloringofgraphswithoutinducedpathsonsevenvertices AT zhongm threecoloringandlistthreecoloringofgraphswithoutinducedpathsonsevenvertices |
| _version_ |
1807316913893670912 |