Coloring Graphs with Constraints on Connectivity
No hay miniatura disponible
Archivos
Fecha
2017-08
Profesor/a Guía
Facultad/escuela
Idioma
en
Título de la revista
ISSN de la revista
Título del volumen
Editor
Wiley-Liss Inc.
Nombre de Curso
Licencia CC
CC BY 4.0 DEED
Atribución 4.0 Internacional
Licencia CC
https://creativecommons.org/licenses/by/4.0/deed.es
Resumen
A 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.
Notas
Indexación: Scopus
Palabras clave
Brooks’ theorem, coloring; local connectivity, local edge-connectivity, minimally k-connected, vertex degree
Citación
Journal of Graph Theory Volume 85, Issue 4, Pages 814 - 838August 2017
DOI
10.1002/jgt.22109