Chromatic boundedness for graphs with spaghetti tree- and path-decompositions
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.