Fraternal Augmentations of graphs, Coloration and Minors

Authors :: Jaroslav Nešetřil
Patrice Ossona de Mendez
Department of Applied Mathematics (KAM) (KAM)
Univerzita Karlova v Praze
Centre d'Analyse et de Mathématique sociales (CAMS)
École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS)
Elsevier
Source :: Proceedings of the Sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Proceedings of the Sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Mar 2007, Prague, Czech Republic. pp.223-230, ⟨10.1016/j.endm.2007.01.030⟩
Publication Year :: 2007
Publisher :: Elsevier BV, 2007.
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, a linear time algorithm to check subgraph isomorphism for a fixed pattern and homomorphism dualities.