Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9514535 | Electronic Notes in Discrete Mathematics | 2005 | 6 Pages |
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, âr(G). We generalize to these classes some results proved for proper minor closed classes and bounded degree graphs, such as the existence of low tree-width colorings and homomorphism dualities.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Jaroslav NeÅ¡etÅil, Patrice Ossona de Mendez,