Linear treewidth–Hadwiger bound for hereditary graph classes
Let be a hereditary graph class. It is -bounded if there is a function such that for every . It is linearly -bounded if there is a constant such that for every . Linear hereditary-class conjecture. Every -bounded hereditary graph class is linearly -bounded. The paper notes that this holds for circle graphs and proves related linear bounds for low-rank perturbations of circle graphs; the general hereditary-class claim remains open.
References
- Rutger Campbell, James Davies, Marc Distel, Bryce Frederickson, J. Pascal Gollin, Kevin Hendrey, Robert Hickingbotham, Sebastian Wiederrecht, David R. Wood and Liana Yepremyan, “Treewidth, Hadwiger Number, and Induced Minors”, arXiv:2410.19295 (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.