Better 3-coloring algorithms: Excluding a triangle and a seven vertex path | ||
| dc.conicet.organizacion | 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 | |
| dc.conicet.organizacion | University of Princeton | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | University of Ghent | |
| dc.conicet.organizacion | Ithaca College | |
| dc.conicet.organizacion | Universitat zu Köln | |
| dc.conicet.organizacion | Universidad de Chile | |
| dc.conicet.organizacion | Lehman College | |
| dc.contributor.author | Bonomo, Flavia | |
| dc.contributor.author | Chudnovsky, Mariana | |
| 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.issued | 2021-01 | |
| 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. | es |
| 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.format | application/pdf | es |
| 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 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0304-3975 | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/173276 | |
| dc.journal.ciudad | Amsterdam | es |
| dc.journal.pagination | 98-115 | es |
| dc.journal.pais | Países Bajos | es |
| dc.journal.title | Theoretical Computer Science | es |
| dc.journal.volume | 850 | es |
| dc.language.iso | eng | es |
| dc.publisher | Elsevier Science | es |
| 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 | |
| dc.rights | info:eu-repo/semantics/restrictedAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-sa/2.5/ar/ | * |
| dc.subject | CERTIFYING ALGORITHM | es |
| dc.subject | FORBIDDEN INDUCED SUBGRAPHS | es |
| dc.subject | GRAPH ALGORITHM | es |
| dc.subject | GRAPH COLORING | es |
| dc.subject.classification | Ciencias de la Computación | es |
| dc.subject.classification | Ciencias de la Computación e Información | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.subject.classification | Matemática Aplicada | es |
| dc.subject.classification | Matemáticas | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | Better 3-coloring algorithms: Excluding a triangle and a seven vertex path | es |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.be7ccc14-aea2-4706-894f-da4284f0c771_B.pdf
- Tamaño:
- 564.12 KB
- Formato:
- Adobe Portable Document Format