Kanté and Kwon's linear rank-width conjecture for vertex-minor-closed classes

From papers

Let a graph class be vertex-minor-closed if every vertex-minor of every graph in the class also belongs to the class. A graph class has bounded linear rank-width if there is a constant bounding the linear rank-width of all its graphs.

Kanté and Kwon's conjecture. A vertex-minor-closed class of graphs has bounded linear rank-width if and only if it does not contain some tree.

This conjecture is part of the structural theory of vertex-minors, paralleling the characterization of bounded rank-width by excluding a circle graph. Its resolution is not specified in the source.

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

Jungho Ahn, Kevin Hendrey, O-joung Kwon and Sang-il Oum, “Unavoidable pivot-minors in graphs of large rank-depth”, arXiv:2507.12697 (2025).

Solutions 0

No solutions have been posted yet.