Coloring Graphs with Constraints on Connectivity

Vista sencilla de ítem
dc.contributor.authorAboulker, Pierre
dc.contributor.authorBrettell, Nick
dc.contributor.authorHavet, Frédéric
dc.contributor.authorMarx, Dániel
dc.contributor.authorTrotignon, Nicolas
dc.date.accessioned2024-04-25T14:27:59Z
dc.date.available2024-04-25T14:27:59Z
dc.date.issued2017-08
dc.descriptionIndexación: Scopus
dc.description.abstractA graph G has maximal local edge-connectivity k if the maximum number of edge-disjoint paths between every pair of distinct vertices x and y is at most k. We prove Brooks-type theorems for k-connected graphs with maximal local edge-connectivity k, and for any graph with maximal local edge-connectivity 3. We also consider several related graph classes defined by constraints on connectivity. In particular, we show that there is a polynomial-time algorithm that, given a 3-connected graph G with maximal local connectivity 3, outputs an optimal coloring for G. On the other hand, we prove, for k≥3, that k-colorability is NP-complete when restricted to minimally k-connected graphs, and 3-colorability is NP-complete when restricted to (k − 3) -connected graphs with maximal local connectivity k. Finally, we consider a parameterization of k-colorability based on the number of vertices of degree at least k + 1, and prove that, even when k is part of the input, the corresponding parameterized problem is FPT. © 2016 Wiley Periodicals, Inc.
dc.description.urihttps://onlinelibrary-wiley-com.recursosbiblioteca.unab.cl/doi/10.1002/jgt.22109
dc.identifier.citationJournal of Graph Theory Volume 85, Issue 4, Pages 814 - 838August 2017
dc.identifier.doi10.1002/jgt.22109
dc.identifier.issn0364-9024
dc.identifier.urihttps://repositorio.unab.cl/handle/ria/56414
dc.language.isoen
dc.publisherWiley-Liss Inc.
dc.rights.licenseCC BY 4.0 DEED Atribución 4.0 Internacional
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/deed.es
dc.subjectBrooks’ theorem
dc.subjectcoloring; local connectivity
dc.subjectlocal edge-connectivity
dc.subjectminimally k-connected
dc.subjectvertex degree
dc.titleColoring Graphs with Constraints on Connectivity
dc.typeArtículo
Archivos
Bloque original
Mostrando 1 - 1 de 1
No hay miniatura disponible
Nombre:
TEXTO EN INGLES
Tamaño:
309.06 KB
Formato:
Adobe Portable Document Format
Descargar
Bloque de licencias
Mostrando 1 - 1 de 1
No hay miniatura disponible
Nombre:
license.txt
Tamaño:
1.71 KB
Formato:
Item-specific license agreed upon to submission
Descripción:
Descargar
Colecciones
FCE - Artículos de Revista