Chromatic boundedness for graphs with spaghetti tree- and path-decompositions
A spaghetti tree-decomposition of a graph is a tree-decomposition rooted at some vertex, such that the bags containing each vertex of induce a directed path when the edges of are oriented away from the root. A path-decomposition of is a tree-decomposition whose underlying tree is a path. Let denote the chromatic number of .
Chromatic boundedness conjecture. There exists a function such that for every and every graph admitting a spaghetti tree-decomposition and a path-decomposition satisfying
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
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.