On nowhere dense graphs

DOI10.1016/j.ejc.2011.01.006zbMath1226.05102OpenAlexW1994264784MaRDI QIDQ2430977

Patrice Ossona de Mendez, Jaroslav Nešetřil

Publication date: 8 April 2011

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejc.2011.01.006

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Density (toughness, etc.) (05C42)

Related Items (55)

Enumeration for FO Queries over Nowhere Dense Graphs ⋮ Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs ⋮ Rainbow independent sets on dense graph classes ⋮ Modeling limits in hereditary classes: reduction and application to trees ⋮ Coloring and Covering Nowhere Dense Graphs ⋮ Kernelization using structural parameters on sparse graph classes ⋮ Reconfiguration on nowhere dense graph classes ⋮ Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs ⋮ 1-subdivisions, the fractional chromatic number and the Hall ratio ⋮ Towards a characterization of universal categories ⋮ Neighbourhood complexity of graphs of bounded twin-width ⋮ Modularity of minor‐free graphs ⋮ First-order limits, an analytical perspective ⋮ On low tree-depth decompositions ⋮ A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth ⋮ Parameterized complexity of generalized domination problems ⋮ Hat Guessing Numbers of Strongly Degenerate Graphs ⋮ A color-avoiding approach to subgraph counting in bounded expansion classes ⋮ Bounds on half graph orders in powers of sparse graphs ⋮ Clustering powers of sparse graphs ⋮ Interpreting nowhere dense graph classes as a classical notion of model theory ⋮ Distance-two coloring of sparse graphs ⋮ How many \(F\)'s are there in \(G\)? ⋮ On the generalised colouring numbers of graphs that exclude a fixed minor ⋮ Confronting intractability via parameters ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Uniform orderings for generalized coloring numbers ⋮ Classes of graphs with low complexity: the case of classes with bounded linear rankwidth ⋮ Characterisations and examples of graph classes with bounded expansion ⋮ FPT algorithms for domination in sparse graphs and beyond ⋮ Polynomial bounds for centered colorings on proper minor-closed graph classes ⋮ On the generalised colouring numbers of graphs that exclude a fixed minor ⋮ Improved Bounds for Centered Colorings ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Conflict free version of covering problems on graphs: classical and parameterized ⋮ On low rank-width colorings ⋮ On the parameterized complexity of \([1,j\)-domination problems] ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Parameterized complexity of conflict-free set cover ⋮ Faster algorithms for counting subgraphs in sparse graphs ⋮ Unnamed Item ⋮ On the treewidth of dynamic graphs ⋮ EXISTENCE OF MODELING LIMITS FOR SEQUENCES OF SPARSE STRUCTURES ⋮ On the Parameterized Complexity of [1,j-Domination Problems] ⋮ Colouring and Covering Nowhere Dense Graphs ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Digraphs of Bounded Width ⋮ Counting Homomorphisms to Sparse Graphs ⋮ Structural Properties of Sparse Graphs ⋮ Erdös--Hajnal Properties for Powers of Sparse Graphs ⋮ Unnamed Item ⋮ Discrete density comonads and graph parameters ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness

Cites Work

This page was built for publication: On nowhere dense graphs