Colouring graphs with constraints on connectivity

Pierre Aboulker (1, 2, 3) , Nick Brettell (4, 5) , Frédéric Havet (2, 1) , Dániel Marx (6) , Nicolas Trotignon (4, 5)

1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
2 COMUE UCA - COMUE Université Côte d'Azur (2015-2019)
3 I3S - Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis
4 LIP - Laboratoire de l'Informatique du Parallélisme
5 MC2 - Modèles de calcul, Complexité, Combinatoire
6 SZTAKI - Institute for Computer Science and Control [Budapest]

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 ≥ 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.

Mots clés: Brooks' theorem; minimally k-connected; vertex degree; local edge-connectivity; local connectivity; colouring

Domaines: Mathématique discrète [cs.DM]

Pierre Aboulker, Nick Brettell, Frédéric Havet, Dániel Marx, Nicolas Trotignon. Colouring graphs with constraints on connectivity. Journal of Graph Theory, 2017, 85 (4), pp.814-838. ⟨10.1002/jgt.22109⟩. ⟨hal-01570035⟩