Kanté and Kwon's linear rank-width conjecture for vertex-minor-closed classes
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.
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
Sign in to submit a solution.
No solutions have been posted yet.