Back to Search Start Over

Colouring graphs with constraints on connectivity

Authors :
Aboulker, Pierre
Brettell, Nick
Havet, Frédéric
Marx, Dániel
Trotignon, Nicolas
Source :
Journal of Graph Theory 85 (2017), 814-838
Publication Year :
2015

Abstract

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 colouring for $G$. On the other hand, we prove, for $k \ge 3$, that $k$-colourability is NP-complete when restricted to minimally $k$-connected graphs, and 3-colourability is NP-complete when restricted to $(k-1)$-connected graphs with maximal local connectivity $k$. Finally, we consider a parameterization of $k$-colourability 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.<br />Comment: The latest version has minor corrections and clarifications

Details

Database :
arXiv
Journal :
Journal of Graph Theory 85 (2017), 814-838
Publication Type :
Report
Accession number :
edsarx.1505.01616
Document Type :
Working Paper
Full Text :
https://doi.org/10.1002/jgt.22109