Coloring Graphs with Constraints on Connectivity

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

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

Citation

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. https://doi.org/10.1002/jgt.22109

• 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
• DOI: https://doi.org/10.1002/jgt.22109
• Public URL: https://durham-repository.worktribe.com/output/1294819
• Related Public URLs: https://arxiv.org/abs/1505.01616