Backbone colouring conjecture for chordal graphs and spanning forests

About 1 year old · traced to

Let GG be a chordal graph and let HH be a spanning forest of GG. Here ‘BBC⁡2(G,H)‘denotestheminimumnumberofcoloursinacolouringof`\operatorname{BBC}_2(G,H)` denotes the minimum number of colours in a colouring of Gsuchthatendpointsofeveryedgeofsuch that endpoints of every edge ofHreceivecoloursdifferingbyatleastreceive colours differing by at least2,and, and \omega(G) is the clique number of GG.

Backbone colouring conjecture.

BBC⁡2(G,H)≤ω(G)+O(1).\operatorname{BBC}_2(G,H)\leq \omega(G)+\mathcal O(1).

The paper presents this as an open conjecture motivated by the bound ω(G)+O(ω(G))\omega(G)+\mathcal O(\sqrt{\omega(G)}) proved for spanning forests. It predicts a constant additive term independent of the chordal graph and its clique number.

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.