Non-realizable colorings for X-rooted Kₖ-minor-free graphs

Conjecture 4 · arXiv:2504.07764

arXiv Conjecture high confidence— first stated 2025-04-10

Authors: Zdeněk Dvořák, Jan M. Swart

Status open high confidence

Conjecture 4 from arXiv:2504.07764 asserts that Theorem 3 of the paper (which generalises the DeVos–Seymour result to X-rooted-K_{k+1}-minor-free K_{k+2}-minor-free graphs) cannot be extended to X-rooted-K_k-minor-free graphs. No follow-up paper resolving or partially settling this conjecture was found in a search of the literature through May 2026. The conjecture is closely related to Holroyd's conjecture, itself proven only for k=3 (Holroyd) and k=4 (Martinsson–Steiner); a full proof of Holroyd's conjecture would imply Conjecture 4.

Reviewer notes. No follow-up found in indexed literature. The paper is recent (April 2025) and the conjecture is explicitly stated as open by the authors. Holroyd's conjecture (proven for k=3,4) implies Conjecture 4 if it holds in full generality, but the general case of Holroyd's conjecture itself remains open.

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

Conjecture. For every integer $k\geq 3$, there exists a set $X$ of vertices and a set $C$ of $k$-colorings of $X$ such that no $X$-rooted-$K_{k}$-minor-free graph $G$ realizes $C$.

Context

The conjecture asserts that Theorem 3 (the generalization of the DeVos–Seymour result to $X$-rooted-$K_{k+1}$-minor-free $K_{k+2}$-minor-free graphs) does not further extend to $X$-rooted-$K_{k}$-minor-free graphs, i.e., reducible configurations cannot exploit the full global structure when the number of colors falls below what Hadwiger's conjecture postulates. Holroyd's conjecture — that if $G$ is $k$-colorable and every $k$-coloring uses all $k$ colors on $X$ then $K_k$ is an $X$-rooted minor of $G$ — would imply this conjecture if true in general.

Source paper

A note on extendable sets of colorings and rooted minors
Zdeněk Dvořák, Jan M. Swart · 2025-04-10
https://arxiv.org/abs/2504.07764