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)

Full work available at URL https://doi.org/10.14279/DEPOSITONCE-5011

zbMATH Keywords

algorithmic graph structure theorybounded degree graphscolouring numbersdense graph classesfinite model theoryfirst-order logicGaifman's locality theoremgraph classes of bounded expansionparameterized complexity theory

Mathematics Subject Classification ID

Quantifier elimination, model completeness, and related topics (03C10) 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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

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

Cited in

(3)

• Enumeration for FO Queries over Nowhere Dense Graphs
• Discrepancy and sparsity
• Compound logics for modification problems

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)