Trotignon's string-graph or biclique-induced-minor conjecture
A hereditary class is a graph class closed under induced subgraphs. A string graph is an intersection graph of curves in the plane, and is the complete bipartite graph with vertices in each part. Trotignon's conjecture. Every hereditary class of unbounded treewidth contains a subclass of string graphs of unbounded treewidth or a induced minor for every . 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
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.