Grad and classes with bounded expansion. I: Decompositions

DOI10.1016/j.ejc.2006.07.013zbMath1156.05056arXivmath/0508323OpenAlexW1978747958MaRDI QIDQ2426456

Patrice Ossona de Mendez, Jaroslav Nešetřil

Publication date: 22 April 2008

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

Full work available at URL: https://arxiv.org/abs/math/0508323

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph minors (05C83)

Related Items

List rankings and on-line list rankings of graphs ⋮ Characterising bounded expansion by neighbourhood complexity ⋮ Rainbow independent sets on dense graph classes ⋮ Chromatic numbers of exact distance graphs ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ Coloring parameters for graphs on surfaces ⋮ A Note on Circular Chromatic Number of Graphs with Large Girth and Similar Problems ⋮ Kernelization using structural parameters on sparse graph classes ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ Harmless sets in sparse classes ⋮ Kernelization and approximation of distance-$r$ independent sets on nowhere dense graphs ⋮ On coloring numbers of graph powers ⋮ 1-subdivisions, the fractional chromatic number and the Hall ratio ⋮ A fast algorithm for the product structure of planar graphs ⋮ The $k$-strong induced arboricity of a graph ⋮ Parameterized extension complexity of independent set and related problems ⋮ Hypertree-depth and minors in hypergraphs ⋮ Towards a characterization of universal categories ⋮ Reconfiguration in bounded bandwidth and tree-depth ⋮ Induced subdivisions and bounded expansion ⋮ Two lower bounds for $p$-centered colorings ⋮ A $p$-centered coloring for the grid using $O(p)$ colors ⋮ Sublinear separators, fragility and subexponential expansion ⋮ Adapted game colouring of graphs ⋮ Forbidden graphs for tree-depth ⋮ On low tree-depth decompositions ⋮ A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth ⋮ Uniqueness and minimal obstructions for tree-depth ⋮ Shallow Minors, Graph Products, and Beyond-Planar Graphs ⋮ Parameterized complexity of generalized domination problems ⋮ Tree-Width and Optimization in Bounded Degree Graphs ⋮ Grad and classes with bounded expansion. II: Algorithmic aspects ⋮ Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities ⋮ Unnamed Item ⋮ A color-avoiding approach to subgraph counting in bounded expansion classes ⋮ Unnamed Item ⋮ On nowhere dense graphs ⋮ Further hardness results on rainbow and strong rainbow connectivity ⋮ Many Facets of Dualities ⋮ Bounds on half graph orders in powers of sparse graphs ⋮ Clustering powers of sparse graphs ⋮ Unnamed Item ⋮ Distance-two coloring of sparse graphs ⋮ Unnamed Item ⋮ How many $F$'s are there in $G$? ⋮ Colouring, constraint satisfaction, and complexity ⋮ Regular partitions of gentle graphs ⋮ Locally identifying coloring in bounded expansion classes of graphs ⋮ Colouring edges with many colours in cycles ⋮ On forbidden subdivision characterizations of graph classes ⋮ Confronting intractability via parameters ⋮ Polynomial treedepth bounds in linear colorings ⋮ Uniform orderings for generalized coloring numbers ⋮ Classes of graphs with low complexity: the case of classes with bounded linear rankwidth ⋮ Degenerate and star colorings of graphs on surfaces ⋮ Characterisations and examples of graph classes with bounded expansion ⋮ First-Order Model-Checking in Random Graphs and Complex Networks ⋮ Efficient Graph Packing via Game Colouring ⋮ Computing tree-depth faster than $2^n$ ⋮ On the weak 2-coloring number of planar graphs ⋮ Polynomial bounds for centered colorings on proper minor-closed graph classes ⋮ Complexity of rainbow vertex connectivity problems for restricted graph classes ⋮ On the generalised colouring numbers of graphs that exclude a fixed minor ⋮ On classes of graphs with strongly sublinear separators ⋮ Maximum Shallow Clique Minors in Preferential Attachment Graphs Have Polylogarithmic Size ⋮ On 1-uniqueness and dense critical graphs for tree-depth ⋮ Improved Bounds for Centered Colorings ⋮ Small graph classes and bounded expansion ⋮ First order properties on nowhere dense structures ⋮ Rank-width and tree-width of $H$-minor-free graphs ⋮ LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth ⋮ Computing vertex-surjective homomorphisms to partially reflexive trees ⋮ Unnamed Item ⋮ On low rank-width colorings ⋮ On the parameterized complexity of $[1,j$-domination problems] ⋮ A distributed low tree-depth decomposition algorithm for bounded expansion classes ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Large Independent Sets in Triangle-Free Planar Graphs ⋮ Unnamed Item ⋮ Strongly Sublinear Separators and Polynomial Expansion ⋮ Where First-Order and Monadic Second-Order Logic Coincide ⋮ EXISTENCE OF MODELING LIMITS FOR SEQUENCES OF SPARSE STRUCTURES ⋮ On the Parameterized Complexity of [1,j-Domination Problems] ⋮ Colouring games on outerplanar graphs and trees ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness ⋮ Structural sparsity of complex networks: bounded expansion in random models and real-world graphs ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Fraternal augmentations, arrangeability and linear Ramsey numbers ⋮ Generalization of transitive fraternal augmentations for directed graphs and its applications ⋮ A surprising permanence of old motivations (a not-so-rigid story) ⋮ Digraphs of Bounded Width ⋮ Obstructions for Tree-depth ⋮ Counting Homomorphisms to Sparse Graphs ⋮ Structural Properties of Sparse Graphs ⋮ Erdös--Hajnal Properties for Powers of Sparse Graphs ⋮ From $\chi$- to $\chi_p$-bounded classes ⋮ Unnamed Item ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness ⋮ Constant round distributed domination on graph classes with bounded expansion

Uses Software

PIGALE

Cites Work

This page was built for publication: Grad and classes with bounded expansion. I: Decompositions