The Grad of a Graph and Classes with Bounded Expansion

DOI10.1016/j.endm.2005.06.018zbMath1182.05102OpenAlexW2018615281MaRDI QIDQ3439315

Jaroslav Nešetřil, Patrice Ossona de Mendez

Publication date: 29 May 2007

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2005.06.018

zbMATH Keywords

homomorphismcoloringtree-depthbounded expansiontransitive fraternal augmentationconstrained orientationrestricted duality

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15)

Related Items (11)

A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth ⋮ Parameterized complexity of generalized domination problems ⋮ Grad and classes with bounded expansion. I: Decompositions ⋮ Grad and classes with bounded expansion. II: Algorithmic aspects ⋮ Bounds on half graph orders in powers of sparse graphs ⋮ How many \(F\)'s are there in \(G\)? ⋮ Colouring edges with many colours in cycles ⋮ Characterisations and examples of graph classes with bounded expansion ⋮ Homomorphism preservation on quasi-wide classes ⋮ A distributed low tree-depth decomposition algorithm for bounded expansion classes ⋮ Fraternal augmentations, arrangeability and linear Ramsey numbers

Cites Work

• Universality of \(A\)-mote graphs
• Graph minors. XVI: Excluding a non-planar graph
• Universal \(H\)-colorable graphs without a given configuration
• Excluding any graph as a minor allows a low tree-width 2-coloring
• Tree-depth, subgraph coloring and homomorphism bounds

This page was built for publication: The Grad of a Graph and Classes with Bounded Expansion