Bounded-mad backbone colouring conjecture for chordal graphs

Let q,dNq,d\in\mathbb N. Let GG be a chordal graph and let HH be a subgraph of GG. Write Mad(H)\operatorname{Mad}(H) for the maximum average degree of HH, and let BBCq(G,H)\operatorname{BBC}_q(G,H) denote the minimum number of colours in a colouring of GG such that endpoints of every edge of HH receive colours differing by at least qq. Then there exists a function

f:N2Nf:\mathbb N^2\to\mathbb N

such that the following holds for every such GG and HH with Mad(H)d\operatorname{Mad}(H)\leq d.

Bounded-mad backbone colouring conjecture.

BBCq(G,H)ω(G)+f(q,d).\operatorname{BBC}_q(G,H)\leq \omega(G)+f(q,d).

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

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.