Grad and classes with bounded expansion I. Decompositions

Jaroslav Nešetřil, Patrice Ossona de Mendez

Type: Article

Publication Date: 2007-04-17

Citations: 192

DOI: https://doi.org/10.1016/j.ejc.2006.07.013

View Publication

Download PDF

Locations

European Journal of Combinatorics - View
arXiv (Cornell University) - View - PDF
CiteSeer X (The Pennsylvania State University) - View - PDF
HAL (Le Centre pour la Communication Scientifique Directe) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Grad and classes with bounded expansion I. decompositions	2005	Jaroslav Nešetřil Patrice Ossona de Mendez
+	Grad and classes with bounded expansion I. decompositions	2005	Jaroslav Nešetřil Patrice Ossona de Mendez
+	Grad and Classes with Bounded Expansion II. Algorithmic Aspects	2005	Jaroslav Nešetřil Patrice Ossona de Mendez
+	Grad and Classes with Bounded Expansion II. Algorithmic Aspects	2005	Jaroslav Nešetřil Patrice Ossona de Mendez
+ PDF Chat	Grad and classes with bounded expansion III. Restricted graph homomorphism dualities	2008	Jaroslav Nešetřil Patrice Ossona de Mendez
+	Grad and classes with bounded expansion III. restricted dualities	2005	Jaroslav Nešetřil Patrice Ossona de Mendez
+	Algorithms for Classes of Graphs with Bounded Expansion	2009	Zdeněk Dvořák Daniel Kráľ
+ PDF Chat	On the generalized coloring numbers	2025	Sebastian Siebertz
+	Vertex-minor-closed classes are $χ$-bounded	2020	James C. Davies
+	Weak coloring numbers of minor-closed graph classes	2024	Jędrzej Hodor Hoang La Piotr Micek Clément Rambaud
+	Vertex-minor-closed classes are $\chi$-bounded	2020	James C. Davies
+	Weak coloring numbers of minor-closed graph classes	2025	Jçdrzej Hodor Hoang La Piotr Micek Clément Rambaud
+ PDF Chat	Explicit bounds for graph minors	2018	Jim Geelen Tony Huynh R. Bruce Richter
+	Chi-boundedness of graph classes excluding wheel vertex-minors	2017	엄상일
+ PDF Chat	Polynomial bounds for centered colorings on proper minor-closed graph classes	2021	Michał Pilipczuk Sebastian Siebertz
+ PDF Chat	A Lower Bound on the Average Degree Forcing a Minor	2020	Sergey Norin Bruce Reed Andrew Thomason David R. Wood
+	On low rank-width colorings	2017	O‐joung Kwon Michał Pilipczuk Sebastian Siebertz
+	Classes of graphs with small rank decompositions are chi-bounded	2011	Zdeněk Dvořák Daniel Kráľ
+ PDF Chat	Treewidth versus clique number: induced minors	2024	Claire Hilaire Martin Milanič Nicolas Trotignon Djordje Vasić
+	Polynomial bounds for centered colorings on proper minor-closed graph classes	2019	Michał Pilipczuk Sebastian Siebertz

Works That Cite This (161)

Action	Title	Year	Authors
+	On forbidden subdivision characterizations of graph classes	2007	Zdeněk Dvořák
+	Sublinear separators, fragility and subexponential expansion	2015	Zdeněk Dvořák
+ PDF Chat	1-Subdivisions, the Fractional Chromatic Number and the Hall Ratio	2020	Zdeněk Dvořák Patrice Ossona de Mendez Hehui Wu
+ PDF Chat	Locally identifying coloring in bounded expansion classes of graphs	2013	Daniel Gonçalves Aline Parreau Alexandre Pinlou
+ PDF Chat	Polynomial bounds for centered colorings on proper minor-closed graph classes	2021	Michał Pilipczuk Sebastian Siebertz
+ PDF Chat	Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions	2015	Eun Jung Kim Alexander Langer Christophe Paul Felix Reidl Peter Rossmanith Ignasi Sau Somnath Sikdar
+	Obstructions for Tree-depth	2009	Archontia C. Giannopoulou Dimitrios M. Thilikos
+ PDF Chat	A Faster Parameterized Algorithm for Treedepth	2014	Felix Reidl Peter Rossmanith Fernando Sánchez Villaamil Somnath Sikdar
+ PDF Chat	EXISTENCE OF MODELING LIMITS FOR SEQUENCES OF SPARSE STRUCTURES	2019	Jaroslav Nešetřil Patrice Ossona de Mendez
+	Lossy kernels for connected distance-$r$ domination on nowhere dense graph classes	2017	Sebastian Siebertz

Works Cited by This (18)

Action	Title	Year	Authors
+	On Star Coloring of Graphs	2001	Guillaume Fertin André Raspaud Bruce Reed
+	Colorings and Homomorphisms of Minor Closed Classes	2003	Jaroslav Nešetřil Patrice Ossona de Mendez
+ PDF Chat	None	1998	Noga Alon T. H. Marshall
+	On acyclic colorings of planar graphs	2006	O. V. Borodin
+	An algorithm for fraternal orientation of graphs	1992	Jorge Urrutia Fǎnicǎ Gavril
+	The Grad of a Graph and Classes with Bounded Expansion	2005	Jaroslav Nešetřil Patrice Ossona de Mendez
+	Excluding any graph as a minor allows a low tree-width 2-coloring	2004	Matt DeVos Guoli Ding Bogdan Oporowski Daniel P. Sanders Bruce Reed Paul Seymour Dirk Vertigan
+	Fraternal Augmentations of graphs, Coloration and Minors	2007	Jaroslav Nešetřil Patrice Ossona de Mendez
+ PDF Chat	Grad and classes with bounded expansion III. Restricted graph homomorphism dualities	2008	Jaroslav Nešetřil Patrice Ossona de Mendez
+	Tree-depth, subgraph coloring and homomorphism bounds	2005	Jaroslav Nešetřil Patrice Ossona de Mendez