Bounded-mad backbone colouring conjecture for chordal graphs
Bounded-mad backbone colouring conjecture for chordal graphs
Let . Let be a chordal graph and let be a subgraph of . Write for the maximum average degree of , and let denote the minimum number of colours in a colouring of such that endpoints of every edge of receive colours differing by at least . Then there exists a function
such that the following holds for every such and with .
Bounded-mad backbone colouring conjecture.
This is stated as a stronger conjecture than the spanning-forest case, since forests have bounded maximum average degree. The source says that the conjecture is believed to hold; no resolution is given.
Sources & referencesView supporting material
Primary source
Júlio Araújo, Nicolas Nisse and Lucas Picasarri-Arrieta, “Backbone colouring of chordal graphs”, arXiv:2508.02980 (2025).
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.