Small graph classes and bounded expansion

DOI10.1016/J.JCTB.2009.06.001MaRDI QIDQ965245zbMATH OpenOpenAlexFDO

Authors Zdeněk Dvořák, Serguei Norine

Publication date 21 April 2010

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jctb.2009.06.001

zbMATH Keywords

graphbounded expansionsmall graph classes

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75)

Recommendations

• Characterisations and examples of graph classes with bounded expansion
• Grad and classes with bounded expansion. I: Decompositions
• Characterising bounded expansion by neighbourhood complexity
• Induced subdivisions and bounded expansion
• A note on sublinear separators and expansion

Cites work

• Grad and classes with bounded expansion. I: Decompositions
• Grad and classes with bounded expansion. II: Algorithmic aspects
• Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities
• Linear time low tree-width partitions and algorithmic consequences
• Proper minor-closed families are small
• Random planar graphs
• Structural Properties of Sparse Graphs
• The asymptotic number of labeled graphs with given degree sequences

Cited in

(12)

• Random graphs from a weighted minor-closed class
• Random graphs containing few disjoint excluded minors
• Characterisations and examples of graph classes with bounded expansion
• A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three
• Characterising bounded expansion by neighbourhood complexity
• A note on circular chromatic number of graphs with large girth and similar problems
• Sublinear separators, fragility and subexponential expansion
• Twin-width II: small classes
• Classes of graphs embeddable in order-dependent surfaces
• Chordal graphs with bounded tree-width
• The small set vertex expansion problem
• On the purity of minor-closed classes of graphs

This page was built for publication: Small graph classes and bounded expansion

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