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:
| Autor principal: | |
|---|---|
| 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: |
| Sumario: | 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. |
|---|