Grad and classes with bounded expansion I. decompositions
| dc.creator | Nesetril, Jaroslav | |
| dc.creator | De Mendez, Patrice Ossona | |
| dc.date | 2005-08-17 | |
| dc.date.accessioned | 2026-07-07T05:22:26Z | |
| dc.date.available | 2026-07-07T05:22:26Z | |
| dc.description | 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, grad r(G). For these classes we prove the existence of several partition results such as the existence of low tree-width and low tree-depth colorings. This generalizes and simplifies several earlier results (obtained for minor closed classes). | |
| dc.identifier | https://arxiv.org/abs/math/0508323 | |
| dc.identifier | http://arxiv.org/abs/math/0508323 | |
| dc.identifier | KAM-DIMATIA Series 2005-739 (2005) 1-21 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/76060 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C15 05C75 | |
| dc.title | Grad and classes with bounded expansion I. decompositions | |
| dc.type | text |