Trotignon's string-graph or biclique-induced-minor conjecture

About 1 year old · traced to

A hereditary class is a graph class closed under induced subgraphs. A string graph is an intersection graph of curves in the plane, and Kℓ,ℓK_{\ell,\ell} is the complete bipartite graph with ℓ\ell vertices in each part. Trotignon's conjecture. Every hereditary class of unbounded treewidth contains a subclass of string graphs of unbounded treewidth or a Kℓ,ℓK_{\ell,\ell} induced minor for every ℓ\ell. The conjecture is refuted in the paper using hereditary classes of unbounded treewidth that contain neither an unbounded-treewidth subclass of string graphs nor arbitrarily large bicliques as induced minors.

References

Primary source

Bogdan Alecu, Édouard Bonnet, Pedro Bureo Villafana and Nicolas Trotignon, “Every Graph is Essential to Large Treewidth”, arXiv:2502.14775 (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.