Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4654411 | European Journal of Combinatorics | 2009 | 8 Pages |
Abstract
We relate the notions of arrangeability and admissibility to bounded expansion classes and prove that these notions can be characterized by ∇1(G)∇1(G). (The Burr–Erdős conjecture relates to ∇0(G)∇0(G).) This implies the linearity of the Ramsey number and the bounded game chromatic number for some new classes of graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Jaroslav Nešetřil, Patrice Ossona de Mendez,