The Grad of a Graph and Classes with Bounded Expansion

DOI10.1016/J.ENDM.2005.06.018MaRDI QIDQ3439315zbMATH OpenOpenAlexFDO

Authors J. Nešetřil, P. 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

bounded expansioncoloringconstrained orientationhomomorphismrestricted dualitytransitive fraternal augmentationtree-depth

Mathematics Subject Classification ID

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

Cites work

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

Cited in

(13)

• Fraternal augmentations, arrangeability and linear Ramsey numbers
• 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
• Parameterized complexity of generalized domination problems
• Colouring edges with many colours in cycles
• A unified approach to structural limits and limits of graphs with bounded tree-depth
• A distributed low tree-depth decomposition algorithm for bounded expansion classes
• How many F's are there in G?
• Bounds on half graph orders in powers of sparse graphs
• Characterisations and examples of graph classes with bounded expansion
• On first-order transductions of classes of graphs
• Homomorphism preservation on quasi-wide classes

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

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