Classes of graphs with low complexity: the case of classes with bounded linear rankwidth

DOI10.1016/J.EJC.2020.103223MaRDI QIDQ2225428zbMATH OpenOpenAlexFDO

Authors J. Nešetřil, P. Ossona de Mendez, Roman Rabinovich, Sebastian Siebertz

Publication date 8 February 2021

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

MSO-transductions of pathsMSO-transductions of trees

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Structural characterization of families of graphs (05C75)

Abstract: Classes with bounded rankwidth are MSO-transductions of trees and classes with bounded linear rankwidth are MSO-transductions of paths -- a result that shows a strong link between the properties of these graph classes considered from the point of view of structural graph theory and from the point of view of finite model theory. We take both views on classes with bounded linear rankwidth and prove structural and model theoretic properties of these classes. The structural results we obtain are the following. 1) The number of unlabeled graphs of order $n$ with linear rank-width at most~$r$ is at most $$. 2) Graphs with linear rankwidth at most $r$ are linearly $chi$-bounded. Actually, they have bounded $c$-chromatic number, meaning that they can be colored with $f(r)$ colors, each color inducing a cograph. 3) To the contrary, based on a Ramsey-like argument, we prove for every proper hereditary family $F$ of graphs (like cographs) that there is a class with bounded rankwidth that does not have the property that graphs in it can be colored by a bounded number of colors, each inducing a subgraph in $F$. From the model theoretical side we obtain the following results: 1) A direct short proof that graphs with linear rankwidth at most $r$ are first-order transductions of linear orders. This result could also be derived from Colcombet's theorem on first-order transduction of linear orders and the equivalence of linear rankwidth with linear cliquewidth. 2) For a class $C$ with bounded linear rankwidth the following conditions are equivalent: a) $C$ is stable, b) $C$ excludes some half-graph as a semi-induced subgraph, c) $C$ is a first-order transduction of a class with bounded pathwidth. These results open the perspective to study classes admitting low linear rankwidth covers.

Recommendations

• On low rank-width colorings
• On low rank-width colorings
• Linear clique-width for hereditary classes of cographs
• Definable decompositions for graphs of bounded linear cliquewidth
• Linear-time algorithms for graphs of bounded rankwidth: a fresh look using game theory (extended abstract)

Cites work

• \(k\)-NLC graphs and polynomial algorithms
• A combinatorial problem; stability and order for models and theories in infinitary languages
• A Combinatorial Theorem for Trees
• A partial k-arboretum of graphs with bounded treewidth
• Approximating clique-width and branch-width
• Classes of graphs with small rank decompositions are \(\chi \)-bounded
• Factorization forests of finite height
• First order properties on nowhere dense structures
• First-order interpretations of bounded expansion classes
• Grad and classes with bounded expansion. I: Decompositions
• Graph minors. I. Excluding a forest
• Graph minors. II. Algorithmic aspects of tree-width
• Graph structure and monadic second-order logic. A language-theoretic approach
• Handle-rewriting hypergraph grammars
• scientific article; zbMATH DE number 1696534 (Why is no real title available?)
• scientific article; zbMATH DE number 3889565 (Why is no real title available?)
• scientific article; zbMATH DE number 7029306 (Why is no real title available?)
• Induced subdivisions and bounded expansion
• Interpreting nowhere dense graph classes as a classical notion of model theory
• Linear layouts measuring neighbourhoods in graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Minimal classes of graphs of unbounded clique-width
• On low rank-width colorings
• On nowhere dense graphs
• On the density of families of sets
• On the number of types in sparse graphs
• On the relationship between NLC-width and linear NLC-width
• On VC-minimal theories and variants
• Partitions of graphs into cographs
• Ramsey-type theorems with forbidden subgraphs
• Second-order quantifiers and the complexity of theories
• Sparsity. Graphs, structures, and algorithms
• Stable graphs
• Structural sparsity
• Testing first-order properties for subclasses of sparse graphs
• The chromatic number and other functions of the lexicographic product
• The Erdős-Hajnal conjecture. A survey
• The Height of Factorization Forests
• The monadic second-order logic of graphs. VII: Graphs as relational structures
• The Ramsey number R(3, t) has order of magnitude t²/log t
• The “Art of Trellis Decoding” Is Fixed-Parameter Tractable
• Tree-depth, subgraph coloring and homomorphism bounds
• Upper bounds to the clique width of graphs
• When trees grow low: shrubs and fast \(\mathrm{MSO}_{1}\)

Cited in

(14)

• On \textsf{NC} algorithms for problems on bounded rank-width graphs
• Obstructions for bounded shrub-depth and rank-depth
• Bounds on half graph orders in powers of sparse graphs
• Dense Induced Subgraphs of Dense Bipartite Graphs
• Tree pivot-minors and linear rank-width
• Harary polynomials
• On low rank-width colorings
• Vertex-minors of graphs: a survey
• Transducing paths in graph classes with unbounded shrubdepth
• Stable graphs of bounded twin-width
• Model checking on interpretations of classes of bounded local cliquewidth
• Decomposition horizons and a characterization of stable hereditary classes of graphs
• A survey of degree-boundedness
• First-order transductions of graphs (invited talk)

This page was built for publication: Classes of graphs with low complexity: the case of classes with bounded linear rankwidth

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