Nowhere dense classes of graphs

DOI10.14279/DEPOSITONCE-5011zbMATH Open1548.05013MaRDI QIDQ6633487FDOQ6633487

Authors: Sebastian Siebertz 

Publication date: 5 November 2024

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

Recommendations

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

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)

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)