Fraternal augmentations of graphs, coloration and minors

Abstract

We introduce classes of graphs with bounded expansion as a generalization of both proper minor closed classes and degree bounded classes. 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.

Keywords

• Fraternal
• augmentations
• graphs
• coloration
• minors