Logarithmic degree-boundedness for intersection graphs of proper minor-closed classes
Logarithmic degree-boundedness for intersection graphs of proper minor-closed classes
A graph class is proper if some graph is not isomorphic to any graph in . Write for the class of intersection graphs of collections of vertex-subsets inducing connected subgraphs of graphs in . Intersection-graph degree conjecture. For every proper minor-closed class of graphs , there is a constant such that every graph has a vertex of degree at most
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.