k-coloring complexity for maximally locally connected graphs

Question 1.7 · arXiv:1505.01616

arXiv Question high confidence— first stated 2016-10-14

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

Status open medium confidence

Question 1.7 asks whether, for fixed k ≥ 4, there is a polynomial-time algorithm for k-colouring k-connected graphs with maximal local (vertex) connectivity k. The source paper settles the k=3 case with a polynomial-time algorithm (the class Ĉ^k_2), but explicitly leaves the case k ≥ 4 open. No subsequent paper resolving or substantially advancing this question was found across five targeted searches covering 2016–2026.

Reviewer notes. No follow-up work found addressing Question 1.7 for k ≥ 4. The question has been open since 2016 (~10 years). Confidence is medium rather than high because the conjecture is old enough that absence of evidence in web search is less conclusive than for a recent paper. The complexity of k-colouring k-connected graphs with maximal local vertex connectivity k for k ≥ 4 remains a natural open problem in structural and algorithmic graph theory.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Question. For fixed $k \geq 4$, is there a polynomial-time algorithm that, given a $k$-connected graph $G$ with maximal local connectivity $k$, finds a $k$-colouring of $G$, or determines that none exists?

Context

Theorem 1.2 gives a polynomial-time algorithm for $k$-colouring when restricted to $\hat{\mathcal{C}}^k_1$ (k-connected graphs with maximal local edge-connectivity $k$). The complexity for the more general class $\hat{\mathcal{C}}^k_2$ (k-connected graphs with maximal local connectivity $k$) remains open for $k \geq 4$.

Also stated in

Colouring graphs with constraints on connectivity (2016-10-14)

Source paper

Colouring graphs with constraints on connectivity
Pierre Aboulker, Nick Brettell, Frédéric Havet, Dániel Marx, Nicolas Trotignon · 2016-10-14
https://arxiv.org/abs/1505.01616 PDF source