Kanté and Kwon's linear rank-width conjecture for vertex-minor-closed classes
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.
References
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).
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.