Mostrar el registro sencillo del ítem
dc.contributor.author
Bonomo, Flavia
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Chudnovsky, Mariana
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Goedgebeur, Jan
dc.contributor.author
Maceli, Peter
dc.contributor.author
Schaudt, Oliver
dc.contributor.author
Stein, Maya
dc.contributor.author
Zhong, Mingxian
dc.date.available
2022-10-14T16:07:12Z
dc.date.issued
2021-01
dc.identifier.citation
Bonomo, Flavia; Chudnovsky, Mariana; Goedgebeur, Jan; Maceli, Peter; Schaudt, Oliver; et al.; Better 3-coloring algorithms: Excluding a triangle and a seven vertex path; Elsevier Science; Theoretical Computer Science; 850; 1-2021; 98-115
dc.identifier.issn
0304-3975
dc.identifier.uri
http://hdl.handle.net/11336/173276
dc.description.abstract
We present an algorithm to color a graph G with no triangle and no induced 7-vertex path (i.e., a {P7,C3}-free graph), where every vertex is assigned a list of possible colors which is a subset of {1,2,3}. While this is a special case of the problem solved in Bonomo et al. (2018) [1], that does not require the absence of triangles, the algorithm here is both faster and conceptually simpler. The complexity of the algorithm is O(|V(G)|5(|V(G)|+|E(G)|)), and if G is bipartite, it improves to O(|V(G)|2(|V(G)|+|E(G)|)). Moreover, we prove that there are finitely many minimal obstructions to list 3-coloring {Pt,C3}-free graphs if and only if t≤7. This implies the existence of a polynomial time certifying algorithm for list 3-coloring in {P7,C3}-free graphs. We furthermore determine other cases of t,ℓ, and k such that the family of minimal obstructions to list k-coloring in {Pt,Cℓ}-free graphs is finite.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Elsevier Science
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.rights
info:eu-repo/semantics/restrictedAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.subject
CERTIFYING ALGORITHM
dc.subject
FORBIDDEN INDUCED SUBGRAPHS
dc.subject
GRAPH ALGORITHM
dc.subject
GRAPH COLORING
dc.subject.classification
Ciencias de la Computación
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
Ciencias de la Computación e Información
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
Matemática Aplicada
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
Matemáticas
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.title
Better 3-coloring algorithms: Excluding a triangle and a seven vertex path
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
2022-09-22T16:16:27Z
dc.journal.volume
850
dc.journal.pagination
98-115
dc.journal.pais
Países Bajos
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.journal.ciudad
Amsterdam
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; Argentina
dc.description.fil
Fil: Chudnovsky, Mariana. University of Princeton; Estados Unidos. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina
dc.description.fil
Fil: Goedgebeur, Jan. University of Ghent; Bélgica
dc.description.fil
Fil: Maceli, Peter. Ithaca 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. Lehman College; Estados Unidos
dc.journal.title
Theoretical Computer Science
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.tcs.2020.10.032
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/abs/pii/S0304397520306150
Archivos asociados