Coloring Graphs with Constraints on Connectivity
Pierre Aboulker, Nick Brettell, Frédéric Havet, Dániel Marx, Nicolas Trotignon · HAL (Le Centre pour la Communication Scientifique Directe) · 2017
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 coloring for G . On the other hand, we prove, for , that k ‐colorability is NP‐complete when restricted to minimally k ‐connected graphs, and 3 ‐colorability is NP‐complete when restricted to ‐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 , and prove that, even when k is part of the input, the corresponding parameterized problem is FPT.