Coloring Graphs with Constraints on Connectivity

Pierre Aboulker, Nick Brettell, Frédéric Havet, Dániel Marx, Nicolas Trotignon

Resultado de la investigación: Contribución a una revistaArtículorevisión exhaustiva

6 Citas (Scopus)

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.

Idioma originalInglés
Páginas (desde-hasta)814-838
Número de páginas25
PublicaciónJournal of Graph Theory
Volumen85
N.º4
DOI
EstadoPublicada - 1 ago 2017
Publicado de forma externa

Áreas temáticas de ASJC Scopus

  • Geometría y topología

Huella

Profundice en los temas de investigación de 'Coloring Graphs with Constraints on Connectivity'. En conjunto forman una huella única.

Citar esto