Trotignon's string-graph or biclique-induced-minor conjecture
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Bogdan Alecu, Édouard Bonnet, Pedro Bureo Villafana and Nicolas Trotignon, “Every Graph is Essential to Large Treewidth”, arXiv:2502.14775 (2025).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.