Tree pivot-minors and linear rank-width

DOI10.1137/21M1402339MaRDI QIDQ5020842zbMATH OpenFDO

Authors Konrad Dabrowski, François Dross, Jisu Jeong, Mamadou Moustapha Kanté, O-joung Kwon, Sang-Il Oum, Daniël Paulusma

Publication date 7 January 2022

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.00561

zbMATH Keywords

linear rank-widthpivot-minortree

Mathematics Subject Classification ID

Trees (05C05) Structural characterization of families of graphs (05C75) Graph minors (05C83)

Abstract: Tree-width and its linear variant path-width play a central role for the graph minor relation. In particular, Robertson and Seymour (1983) proved that for every tree~$T$, the class of graphs that do not contain $T$ as a minor has bounded path-width. For the pivot-minor relation, rank-width and linear rank-width take over the role from tree-width and path-width. As such, it is natural to examine if for every tree~$T$, the class of graphs that do not contain $T$ as a pivot-minor has bounded linear rank-width. We first prove that this statement is false whenever $T$ is a tree that is not a caterpillar. We conjecture that the statement is true if $T$ is a caterpillar. We are also able to give partial confirmation of this conjecture by proving: (1) for every tree $T$, the class of $T$-pivot-minor-free distance-hereditary graphs has bounded linear rank-width if and only if $T$ is a caterpillar; (2) for every caterpillar $T$ on at most four vertices, the class of $T$-pivot-minor-free graphs has bounded linear rank-width. To prove our second result, we only need to consider $T=P_4$ and $T=K_{1,3}$, but we follow a general strategy: first we show that the class of $T$-pivot-minor-free graphs is contained in some class of $(H_1,H_2)$-free graphs, which we then show to have bounded linear rank-width. In particular, we prove that the class of $(K_3,S_{1,2,2})$-free graphs has bounded linear rank-width, which strengthens a known result that this graph class has bounded rank-width.

Recommendations

• Graphs of small rank-width are pivot-minors of graphs of small tree-width
• Linear rank-width and linear clique-width of trees
• Rank-width and tree-width of \(H\)-minor-free graphs
• Tree-depth and vertex-minors
• Linear rank-width and linear clique-width of trees

Cites work

• A Combinatorial Decomposition Theory
• Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
• Approximating clique-width and branch-width
• Between clique-width and linear clique-width of bipartite graphs
• Bipartite graphs without a skew star
• Bounding the mim‐width of hereditary graph classes
• Circle graph obstructions
• Classes of graphs with low complexity: the case of classes with bounded linear rankwidth
• Classifying the clique-width of \(H\)-free bipartite graphs
• Clique-width and edge contraction
• Clique-width for hereditary graph classes
• Colouring diamond-free graphs
• Computing small pivot-minors
• Edge dominating set and colorings on graphs with fixed clique-width
• Excluding a bipartite circle graph from line graphs
• Graph isomorphism for \((H_1, H_2)\)-free graphs: an almost complete dichotomy
• Graph minors. I. Excluding a forest
• Graph minors. V. Excluding a planar graph
• Graph minors. XX: Wagner's conjecture
• Graphs of small rank-width are pivot-minors of graphs of small tree-width
• scientific article; zbMATH DE number 15493 (Why is no real title available?)
• scientific article; zbMATH DE number 2044928 (Why is no real title available?)
• scientific article; zbMATH DE number 1534645 (Why is no real title available?)
• Letter graphs and geometric grid classes of permutations: characterization and recognition
• Linear clique-width for hereditary classes of cographs
• Linear rank-width and linear clique-width of trees
• Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions
• Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm
• Linear time solvable optimization problems on graphs of bounded clique-width
• Matroid Pathwidth and Code Trellis Complexity
• Minimal acyclic forbidden minors for the family of graphs with bounded path-width
• MSOL partitioning problems on graphs of bounded treewidth and clique-width
• Obstructions for bounded shrub-depth and rank-depth
• Obstructions for linear rank-width at most 1
• Quickly excluding a forest
• Rank-width and vertex-minors
• Rank-width: algorithmic and structural results
• Steiner trees for hereditary graph classes: a treewidth perspective
• The “Art of Trellis Decoding” Is Fixed-Parameter Tractable
• THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES
• The Complexity of the Partial Order Dimension Problem
• The grid theorem for vertex-minors
• Thread graphs, linear rank-width and their algorithmic applications
• Transforming trees by successive local complementations
• Upper bounds to the clique width of graphs

Cited in

(10)

• Computing small pivot-minors
• Rank connectivity and pivot-minors of graphs
• Linear rank-width and linear clique-width of trees
• Graphs of small rank-width are pivot-minors of graphs of small tree-width
• Tree-depth and vertex-minors
• Linear rank-width and linear clique-width of trees
• Vertex-minors of graphs: a survey
• Tree pivot-minors and linear rank-width
• Computing pivot-minors
• Linearity of grid minors in treewidth with applications through bidimensionality

This page was built for publication: Tree pivot-minors and linear rank-width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5020842)