Grad and classes with bounded expansion I. decompositions

2005/08/17 by Jaroslav Nesetril, Patrice Ossona De Mendez · 3 citations
Mathematics · #math.CO #msc:05C15 #msc:05C75

paper · pdf

published as KAM-DIMATIA Series 2005-739 (2005) 1-21

arxiv created 2005/08/17 · arxiv updated 2009/12/01

Abstract

We introduce classes of graphs with bounded expansion as a generalization of both proper minor closed classes and degree bounded classes. Such classes are based on a new invariant, the greatest reduced average density (grad) of G with rank r, grad r(G). For these classes we prove the existence of several partition results such as the existence of low tree-width and low tree-depth colorings. This generalizes and simplifies several earlier results (obtained for minor closed classes).

Cited by

• Polynomial bounds for pathwidth
• Treedepth Inapproximability and Exponential ETH Lower Bound
• Decomposing graphs into stable and ordered parts

Related

• Grad and Classes with Bounded Expansion II. Algorithmic Aspects
• Grad and classes with bounded expansion III. restricted dualities
• On low rank-width colorings
• Induced subdivisions and bounded expansion
• Path degeneracy and applications