χ-boundedness via spaghetti and path-decomposition intersection

Conjecture 3 · arXiv:1703.07871

arXiv Conjecture high confidence— first stated 2018-01-29

Authors: Stefan Felsner, Gwenaël Joret, Piotr Micek, William T. Trotter, Veit Wiechert

Status open medium confidence

Conjecture 3 from arXiv:1703.07871 asks whether the chromatic number of any graph admitting both a spaghetti tree-decomposition and a path-decomposition with pairwise bag intersections of size at most k is bounded by a function of k alone. The paper itself disproves the analogous statement for two general tree-decompositions (using Burling graph constructions), making this conjecture the natural boundary between positive and negative results. No follow-up paper resolving the conjecture — either by proving or disproving it — was found in five targeted web searches spanning the relevant literature up to 2026.

Reviewer notes. The paper disproves the two-tree-decomposition analogue of Asplund–Grünbaum using Burling graphs. Conjecture 3 proposes that restricting one decomposition to be a spaghetti tree-decomposition (where each vertex's bags form a directed path from the root) suffices to recover χ-boundedness. The related survey arXiv:2002.05363 (Huynh, Reed, Wood, Yepremyan, 'Notes on Tree- and Path-chromatic Number') covers the broader area but does not appear to address spaghetti tree-decompositions specifically. No resolution was found; the conjecture appears open as of May 2026.

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

Conjecture. There exists a function $f : \mathbb{N} \to \mathbb{N}$ such that $\chi(G) \leq f(k)$ for every $k \geq 1$ and every graph $G$ admitting a spaghetti tree-decomposition $(T, \{B_t\}_{t \in V(T)})$ and a path-decomposition $(P, \{B_p\}_{p \in V(P)})$ such that $|B_t \cap B_p| \leq k$ for every $t \in V(T)$ and $p \in V(P)$.

Context

The authors conclude the paper with this conjecture as an open problem in the spirit of exploring how the Asplund–Grünbaum result could be extended. A spaghetti tree-decomposition is a tree-decomposition rooted at some vertex $r$ such that, orienting edges away from $r$, the subtree induced by bags containing any fixed vertex $v$ forms a directed path. The authors remark that the conjecture could even hold with two spaghetti tree-decompositions.

Source paper

Burling graphs, chromatic number, and orthogonal tree-decompositions
Stefan Felsner, Gwenaël Joret, Piotr Micek, William T. Trotter, Veit Wiechert · 2018-01-29
https://arxiv.org/abs/1703.07871 PDF source