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

About 9 years old · traced to

A spaghetti tree-decomposition of a graph GG is a tree-decomposition (T,{Bt}t∈V(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:N→Nf:\mathbb{N}\to\mathbb{N} such that χ(G)≤f(k)\chi(G)\leq f(k) for every k≥1k\geq 1 and every graph GG admitting a spaghetti tree-decomposition (T,{Bt}t∈V(T))(T,\{B_t\}_{t\in V(T)}) and a path-decomposition (P,{Bp}p∈V(P))(P,\{B_p\}_{p\in V(P)}) satisfying

∣Bt∩Bp∣≤kfor every t∈V(T) and p∈V(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.

References

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.