Twin-width II: small classes

DOI10.5070/C62257876OpenAlexW3036859171MaRDI QIDQ5051371

Rémi Watrigant, Édouard Bonnet, Eun Jung Kim, Colin Geniet, Steéphan Thomassé

Publication date: 23 November 2022

Published in: Combinatorial Theory (Search for Journal in Brave)

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

zbMATH Keywords

expanderssparsitysmall classestwin-widthclique subdivisions

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Expander graphs (05C48)

Related Items (8)

Bounds for the Twin-Width of Graphs ⋮ Twin-width can be exponential in treewidth ⋮ Graphs of bounded twin-width are quasi-polynomially \(\chi \)-bounded ⋮ Twin-width and transductions of proper \(k\)-mixed-thin graphs ⋮ Neighbourhood complexity of graphs of bounded twin-width ⋮ Functionality of box intersection graphs ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ Graph parameters, implicit representations and factorial properties

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sparsity. Graphs, structures, and algorithms
• Coloring intersection graphs of \(x\)-monotone curves in the plane
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Lifts, discrepancy and nearly optimal spectral gap
• Small graph classes and bounded expansion
• Cleaning interval graphs
• Polynomial bounds for centered colorings on proper minor-closed graph classes
• Proper minor-closed families are small
• Strongly Sublinear Separators and Polynomial Expansion
• Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs
• On the Monadic Second-Order Transduction Hierarchy
• Implicat Representation of Graphs
• Better upper bounds on the Füredi-Hajnal limits of permutations
• Optimal Induced Universal Graphs and Adjacency Labeling for Trees
• Adjacency Labelling for Planar Graphs (and Beyond)
• First-Order Interpretations of Bounded Expansion Classes
• Planar Graphs Have Bounded Queue-Number
• Finding small patterns in permutations in linear time
• Algorithms – ESA 2005
• The number of labeled k-dimensional trees
• Clustered 3-colouring graphs of bounded degree
• Graph product structure for non-minor-closed classes

This page was built for publication: Twin-width II: small classes