Degenerate-graph density conjecture

For kN0k\in\mathbb{N}_0, let Dk\mathcal{D}_k be the class of kk-degenerate graphs. Let fk(H)f_k(H) be the separation parameter defined by taking fk(H)=1f_k(H)=1 when HH has no (k)(\leqslant k)-separation, and otherwise taking the maximum number of pairwise independent (k)(\leqslant k)-separations in HH.

Degenerate-graph density conjecture. For every fixed kk-degenerate graph HH,

C(H,Dk,n)Θ(nfk(H)).C(H,\mathcal{D}_k,n) \in \Theta\left(n^{f_k(H)}\right).

This is proposed as a generalisation of the paper's bounds for degenerate graph classes. The source does not report a proof or disproof, so the conjecture remains open.

Sources & referencesView supporting material

Primary source

Tony Huynh and David R. Wood, “Tree densities in sparse graph classes”, arXiv:2009.12989 (2021).

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.