Chromatic boundedness for graphs with spaghetti tree- and path-decompositions

A spaghetti tree-decomposition of a graph GG is a tree-decomposition (T,{Bt}tV(T))(T,\{B_t\}_{t\in V(T)}) rooted at some vertex, such that the bags containing each vertex of GG induce a directed path when the edges of TT are oriented away from the root. A path-decomposition of GG is a tree-decomposition whose underlying tree is a path. Let χ(G)\chi(G) denote the chromatic number of GG.

Chromatic boundedness conjecture. There exists a function f:NNf:\mathbb{N}\to\mathbb{N} such that χ(G)f(k)\chi(G)\leq f(k) for every k1k\geq 1 and every graph GG admitting a spaghetti tree-decomposition (T,{Bt}tV(T))(T,\{B_t\}_{t\in V(T)}) and a path-decomposition (P,{Bp}pV(P))(P,\{B_p\}_{p\in V(P)}) satisfying

BtBpkfor every tV(T) and pV(P).|B_t\cap B_p|\leq k\qquad\text{for every }t\in V(T)\text{ and }p\in V(P).

This asks whether the chromatic number is bounded solely in terms of the maximum intersection size between the bags of the two decompositions, extending the use of tree-decomposition methods in bounding chromatic number. The source presents it as an open problem and gives no resolution.

Sources & referencesView supporting material

Primary source

Stefan Felsner, Gwenaël Joret, Piotr Micek, William T. Trotter and Veit Wiechert, “Burling graphs, chromatic number, and orthogonal tree-decompositions”, arXiv:1703.07871 (2018).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.