Backbone colouring conjecture for chordal graphs and spanning forests

Let GG be a chordal graph and let HH be a spanning forest of GG. Here BBC2(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.

BBC2(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.

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.