Mostrar el registro sencillo del ítem

dc.contributor.author
Bonomo, Flavia  
dc.contributor.author
Chudnovsky, Mariana  
dc.contributor.author
Maceli, Peter  
dc.contributor.author
Schaudt, Oliver  
dc.contributor.author
Stein, Maya  
dc.contributor.author
Zhong, Mingxian  
dc.date.available
2020-02-10T20:31:12Z  
dc.date.issued
2018-08  
dc.identifier.citation
Bonomo, Flavia; Chudnovsky, Mariana; Maceli, Peter; Schaudt, Oliver; Stein, Maya; et al.; Three-coloring and list three-coloring of graphs without induced paths on seven vertices; Springer; Combinatorica; 38; 4; 8-2018; 779-801  
dc.identifier.issn
0209-9683  
dc.identifier.uri
http://hdl.handle.net/11336/97122  
dc.description.abstract
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.  
dc.format
application/pdf  
dc.language.iso
eng  
dc.publisher
Springer  
dc.rights
info:eu-repo/semantics/openAccess  
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/  
dc.subject
3-coloring  
dc.subject
list 3-coloring  
dc.subject
P7-free graph  
dc.subject
polynomial time algorithm  
dc.subject.classification
Ciencias de la Computación  
dc.subject.classification
Ciencias de la Computación e Información  
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS  
dc.subject.classification
Matemática Aplicada  
dc.subject.classification
Matemáticas  
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS  
dc.title
Three-coloring and list three-coloring of graphs without induced paths on seven vertices  
dc.type
info:eu-repo/semantics/article  
dc.type
info:ar-repo/semantics/artículo  
dc.type
info:eu-repo/semantics/publishedVersion  
dc.date.updated
2019-12-16T19:15:29Z  
dc.journal.volume
38  
dc.journal.number
4  
dc.journal.pagination
779-801  
dc.journal.pais
Alemania  
dc.journal.ciudad
Berlín  
dc.description.fil
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; Argentina  
dc.description.fil
Fil: Chudnovsky, Mariana. University of Princeton; Estados Unidos  
dc.description.fil
Fil: Maceli, Peter. Canisius College; Estados Unidos  
dc.description.fil
Fil: Schaudt, Oliver. Universitat zu Köln; Alemania  
dc.description.fil
Fil: Stein, Maya. Universidad de Chile; Chile  
dc.description.fil
Fil: Zhong, Mingxian. Columbia University; Estados Unidos  
dc.journal.title
Combinatorica  
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1007/s00493-017-3553-8  
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://link.springer.com/article/10.1007%2Fs00493-017-3553-8  

Archivos asociados
Thumbnail
 
Tamaño: 466.0Kb
Formato: PDF
.