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

Never refreshed

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.