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

From papers

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.

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

No solutions have been posted yet.