Nowhere dense classes of graphs

DOI10.14279/DEPOSITONCE-5011MaRDI QIDQ6633487zbMATH OpenFDO

Authors Sebastian Siebertz

Publication date 5 November 2024

Published in Foundations of Computing (Search for Journal in Brave)

zbMATH Keywords

finite model theoryfirst-order logicbounded degree graphsalgorithmic graph structure theoryparameterized complexity theorygraph classes of bounded expansioncolouring numbersGaifman's locality theoremdense graph classes

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Planar graphs; geometric and topological aspects of graph theory (05C10) Density (toughness, etc.) (05C42) Structural characterization of families of graphs (05C75) Graph minors (05C83) Quantifier elimination, model completeness, and related topics (03C10)

Recommendations

• First order properties on nowhere dense structures
• Testing first-order properties for subclasses of sparse graphs
• On nowhere dense graphs

Cited in

(2)

• Enumeration for FO Queries over Nowhere Dense Graphs
• Discrepancy and sparsity

This page was built for publication: Nowhere dense classes of graphs

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