Characterization of (CC) for coloring parameters

Open Problem: Characterization of parameters satisfying (CC) · arXiv:1801.06824

arXiv Informal medium confidence— first stated 2019-02-26

Authors: Zdeněk Dvořák, Jakub Pekárek, Jean-Sébastien Sereni

Status open high confidence

The open problem from arXiv:1801.06824 asks to characterize the hereditary, connected graph parameters f satisfying property (CC): for all p, s there exist p', s' such that col_{f,p'}(G) ≤ s' whenever χ^ℓ_{f,p}(G) ≤ s. The authors showed the fan parameter does not satisfy (CC) and gave two sufficient conditions covering all previously studied parameters, but left the full characterization open. A broad web search (5 calls) found no subsequent paper resolving this characterization; the only citing work identified (Cho–Choi–Jiang–Kim–Park–Yan–Zhu 2020 on generalized list colouring) could not be verified as addressing property (CC) directly. The problem appears to remain open as of May 2026.

Reviewer notes. No follow-up paper addressing the characterization of parameters satisfying (CC) was found in the indexed literature. The Semantic Scholar citation API returned only two citing papers (a 2020 generalized list colouring paper whose relevance to property (CC) could not be verified, and an earlier unrelated paper by Dvořák–Norin). The conjecture is recent (2019) and niche enough that absence of evidence is consistent with it being genuinely open.

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

Informal. Characterize the (hereditary, connected) graph parameters $f$ satisfying property (CC): for all integers $p$ and $s$, there exist two integers $p'$ and $s'$ such that $\mathrm{col}_{f,p'}(G) \leq s'$ for every graph $G$ satisfying $\chi^\ell_{f,p}(G) \leq s$.

Context

The authors show that the fan parameter does not satisfy (CC) (Lemma 2), and provide two sufficient conditions (via property (CD) and via Lemma 4) covering all parameters previously studied in the literature, but explicitly state they were unable to fully describe the class of parameters satisfying (CC). This leaves the characterization problem open.

Notes. Stated in prose without a labelled environment: 'While we were unable to fully describe the graph parameters satisfying (CC), we provide two sufficient conditions…'. The paper text appears truncated before Section 2, so additional conjectures or open problems in later sections may not be visible in the supplied text.

Source paper

On generalized choice and coloring numbers
Zdeněk Dvořák, Jakub Pekárek, Jean-Sébastien Sereni · 2019-02-26
https://arxiv.org/abs/1801.06824 PDF source