Skip to main content

Research Repository

Advanced Search

Coloring Graphs with Constraints on Connectivity

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

Coloring Graphs with Constraints on Connectivity Thumbnail


Pierre Aboulker

Nick Brettell

Frédéric Havet

Dániel Marx

Nicolas Trotignon


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 urn:x-wiley:03649024:media:jgt22109:jgt22109-math-0001, that k‐colorability is NP‐complete when restricted to minimally k‐connected graphs, and 3‐colorability is NP‐complete when restricted to urn:x-wiley:03649024:media:jgt22109:jgt22109-math-0002‐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 urn:x-wiley:03649024:media:jgt22109:jgt22109-math-0003, and prove that, even when k is part of the input, the corresponding parameterized problem is FPT.


Aboulker, P., Brettell, N., Havet, F., Marx, D., & Trotignon, N. (2016). Coloring Graphs with Constraints on Connectivity. Journal of Graph Theory, 85(4), 814-838.

Journal Article Type Article
Online Publication Date Dec 5, 2016
Publication Date Aug 31, 2016
Deposit Date Aug 20, 2019
Publicly Available Date Sep 12, 2019
Journal Journal of Graph Theory
Print ISSN 0364-9024
Electronic ISSN 1097-0118
Publisher Wiley
Peer Reviewed Peer Reviewed
Volume 85
Issue 4
Pages 814-838
Related Public URLs


Accepted Journal Article (316 Kb)

Copyright Statement
This is the accepted version of the following article: Aboulker, Pierre, Brettell, Nick, Havet, Frédéric, Marx, Dániel & Trotignon, Nicolas (2017). Coloring Graphs with Constraints on Connectivity. Journal of Graph Theory 85(4): 814-838, which has been published in final form at This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for self-archiving.

You might also like

Downloadable Citations