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

DOI10.1016/j.ejc.2020.103223zbMath1458.05226arXiv1909.01564OpenAlexW3080820494MaRDI QIDQ2225428

Sebastian Siebertz, Roman Rabinovich, Patrice Ossona de Mendez, Jaroslav Nešetřil

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

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

Related Items

Harary polynomials ⋮ Bounds on half graph orders in powers of sparse graphs ⋮ Obstructions for bounded shrub-depth and rank-depth ⋮ Dense Induced Subgraphs of Dense Bipartite Graphs ⋮ Tree Pivot-Minors and Linear Rank-Width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On VC-minimal theories and variants
• Classes of graphs with small rank decompositions are \(\chi \)-bounded
• Sparsity. Graphs, structures, and algorithms
• Partitions of graphs into cographs
• Minimal classes of graphs of unbounded clique-width
• Factorization forests of finite height
• Graph minors. I. Excluding a forest
• Second-order quantifiers and the complexity of theories
• The monadic second-order logic of graphs. VII: Graphs as relational structures
• A partial k-arboretum of graphs with bounded treewidth
• \(k\)-NLC graphs and polynomial algorithms
• Induced subdivisions and bounded expansion
• The chromatic number and other functions of the lexicographic product
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• Grad and classes with bounded expansion. I: Decompositions
• On nowhere dense graphs
• Interpreting nowhere dense graph classes as a classical notion of model theory
• Tree-depth, subgraph coloring and homomorphism bounds
• Approximating clique-width and branch-width
• Linear layouts measuring neighbourhoods in graphs
• A combinatorial problem; stability and order for models and theories in infinitary languages
• On the density of families of sets
• On the relationship between NLC-width and linear NLC-width
• Structural sparsity
• The Erdös-Hajnal Conjecture-A Survey
• When Trees Grow Low: Shrubs and Fast MSO1
• The Height of Factorization Forests
• Graph minors. II. Algorithmic aspects of tree-width
• Stable graphs
• The “Art of Trellis Decoding” Is Fixed-Parameter Tractable
• Deciding First-Order Properties of Nowhere Dense Graphs
• The Ramsey number R(3, t) has order of magnitude t²/log t
• First order properties on nowhere dense structures
• On the number of types in sparse graphs
• Testing first-order properties for subclasses of sparse graphs
• A Combinatorial Theorem for Trees
• On low rank-width colorings
• Ramsey-type theorems with forbidden subgraphs