Logarithmic degree-boundedness for intersection graphs of proper minor-closed classes

A graph class F\mathcal{F} is proper if some graph is not isomorphic to any graph in F\mathcal{F}. Write (F)\int(\mathcal{F}) for the class of intersection graphs of collections of vertex-subsets inducing connected subgraphs of graphs in F\mathcal{F}. Intersection-graph degree conjecture. For every proper minor-closed class of graphs F\mathcal{F}, there is a constant c=c(F)c=c(\mathcal{F}) such that every graph G(F)G\in \int(\mathcal{F}) has a vertex of degree at most

cτ(G)log(τ(G)).c\tau(G)\log(\tau(G)).

The conjecture proposes a uniform growth rate for degree-bounding functions of these intersection-graph classes. The source notes that degree-boundedness is known, while this stronger quantitative bound remains open.

Sources & referencesView supporting material

Primary source

Xiying Du and Rose McCarty, “A survey of degree-boundedness”, arXiv:2403.05737 (2024).

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.