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

homomorphismtree-depthcoloringbounded expansiontransitive fraternal augmentationconstrained orientationrestricted duality

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)

• On first-order transductions of classes of graphs
• Fraternal augmentations, arrangeability and linear Ramsey numbers
• Characterisations and examples of graph classes with bounded expansion
• Parameterized complexity of generalized domination problems
• A distributed low tree-depth decomposition algorithm for bounded expansion classes
• Homomorphism preservation on quasi-wide classes
• Colouring edges with many colours in cycles
• Grad and classes with bounded expansion. I: Decompositions
• Grad and classes with bounded expansion. II: Algorithmic aspects
• A unified approach to structural limits and limits of graphs with bounded tree-depth
• Bounds on half graph orders in powers of sparse graphs
• How many \(F\)'s are there in \(G\)?
• Bounds on half graph orders in powers of sparse graphs

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)