Bounded-mad backbone colouring conjecture for chordal graphs

About 1 year old · traced to

Let q,d∈Nq,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 BBC⁡q(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:N2→Nf:\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.

BBC⁡q(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.

References

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.