Fraternal Augmentations of graphs,Coloration and Minors |
| |
Institution: | Department of Applied Mathematics and Institute of Theoretical Computer Science, Charles University, Praha, Czech Republic;Centre d''Analyse et de Mathématiques Sociales – CNRS, UMR 8557, École des Hautes Études en Sciences Sociales, Paris, France |
| |
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, . 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: | |
本文献已被 ScienceDirect 等数据库收录! |
|