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

Let TT be a tree. A graph is TT-vertex-minor-free if it does not contain TT as a vertex-minor, and linear rank-width is the graph width parameter used in the claim.

Kanté and Kwon's conjecture. For every tree TT, the class of TT-vertex-minor-free graphs has bounded linear rank-width.

The conjecture is known for graph classes whose prime graphs under split decompositions have bounded linear rank-width, including distance-hereditary graphs, and for every tree TT that is a path. The full assertion remains open.

Sources & referencesView supporting material

Primary source

Konrad K. Dabrowski, François Dross, Jisu Jeong, Mamadou Moustapha Kanté, O-joung Kwon, Sang-il Oum and Daniël Paulusma, “Tree pivot-minors and linear rank-width”, arXiv:2008.00561 (2021).

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.