×

zbMATH — the first resource for mathematics

Grad and classes with bounded expansion. I: Decompositions. (English) Zbl 1156.05056
Summary: 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, \nabla_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).

MSC:
05C83 Graph minors
05C75 Structural characterization of families of graphs
Software:
PIGALE
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Albertson, M.O.; Chappell, G.G.; Kierstead, H.A.; Kündgen, A.; Ramamurthi, R., Coloring with no 2-colored P4 ’s, Electronic journal of combinatorics, 11, 1, R26, (2004) · Zbl 1053.05045
[2] Alon, N.; Marshall, T.H., Homomorphisms of edge-colored graphs and Coxeter groups, Journal of algebraic combinatorics, 8, 5-13, (1998) · Zbl 0911.05034
[3] Alon, N.; Mohar, B.; Sanders, D.P., On acyclic colorings of graphs on surfaces, Israel journal of mathematics, 94, 273-283, (1994) · Zbl 0857.05033
[4] Borodin, O.V., On acyclic colorings of planar graphs, Discrete mathematics, 25, 3, 211-236, (1979) · Zbl 0406.05031
[5] Courcelle, B., (), 142-193
[6] Courcelle, B., The monadic second-order logic of graphs I: recognizable sets of finite graphs, Information computation, 85, 12-75, (1990) · Zbl 0722.03008
[7] Deogun, J.S.; Kloks, T.; Kratsch, D.; Muller, H., On vertex ranking for permutation and other graphs, (), 747-758 · Zbl 0941.05516
[8] DeVos, M.; Ding, G.; Oporowski, B.; Sanders, D.P.; Reed, B.; Seymour, P.D.; Vertigan, D., Excluding any graph as a minor allows a low tree-width 2-coloring, Journal of combinatorial theory, series B, 91, 25-41, (2004) · Zbl 1042.05036
[9] Fertin, G.; Raspaud, A.; Reed, B., On star coloring of graphs, (), 140-153 · Zbl 1042.68628
[10] Gavril, F.; Urrutia, J., An algorithm for fraternal orientation of graphs, Information processing letters, 41, 271-274, (1992) · Zbl 0764.68135
[11] Grünbaum, B., Acyclic colorings of planar graphs, Israel journal of mathematics, 14, 390-408, (1973) · Zbl 0265.05103
[12] Halin, R., \(S\)-functions for graphs, Journal of geometry, 8, 171-176, (1976) · Zbl 0339.05108
[13] Kostochka, A., On the minimum of the hadwiger number for graphs with given average degree, Metody diskretnogo analiza, 38, 37-58, (1982), (in Russian). English translation: AMS Translations (2) 132 (1986) 15-32 · Zbl 0544.05037
[14] Mader, W., Homomorphiesätze für graphen, Mathematische annalen, 178, 154-168, (1968) · Zbl 0165.57401
[15] J. Nešetřil, P. Ossona de Mendez, Grad and classes with bounded expansion IV. Structural extensions (in preparation)
[16] Nešetřil, J.; Ossona de Mendez, P., Colorings and homomorphisms of minor closed classes, (), 651-664 · Zbl 1071.05526
[17] Nešetřil, J.; Ossona de Mendez, P., Aspects algorithmiques des classes d’expansion borne, (), 55-58
[18] Nešetřil, J.; Ossona de Mendez, P., Grad and classes with bounded expansion II. algorithmic aspects, European journal of combinatorics, 29, 3, 777-791, (2008) · Zbl 1185.05131
[19] J. Nešetřil, P. Ossona de Mendez, Grad and classes with bounded expansion III. Restricted dualities, European Journal of Combinatorics (2005) (submitted for publication)
[20] Nešetřil, J.; Ossona de Mendez, P., The Grad of a graph and classes with bounded expansion, (), 101-106 · Zbl 1182.05102
[21] Nešetřil, J.; Ossona de Mendez, P., Linear time low tree-width partitions and algorithmic consequences, (), 391-400 · Zbl 1301.05268
[22] Nešetřil, J.; Ossona de Mendez, P., Low tree-depth partitions of classes with bounded expansion, (), 76-81
[23] Nešetřil, J.; Ossona de Mendez, P., Tree depth, subgraph coloring and homomorphism bounds, European journal of combinatorics, 27, 6, 1022-1041, (2006) · Zbl 1089.05025
[24] Nešetřil, J.; Ossona de Mendez, P., Fraternal augmentations of graphs, coloration and minors, (), 223-230 · Zbl 1213.05095
[25] Robertson, N.; Seymour, P.D., Graph minors. I. excluding a forest, Journal of combinatorial theory, series B, 35, 39-61, (1983) · Zbl 0521.05062
[26] Robertson, N.; Seymour, P.D., Graph minors. XVI. excluding a non-planar graph, Journal of combinatorial theory, series B, 89, 1, 43-76, (2003) · Zbl 1023.05040
[27] Schaffer, P., Optimal node ranking of trees in linear time, Information processing letters, 33, 91-96, (1989-90) · Zbl 0683.68038
[28] Skrien, D.J., A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular arc graphs, and nested interval graphs, Journal of graph theory, 6, 3, 309-316, (1982) · Zbl 0495.05027
[29] Thomason, A., An extremal function for contractions of graphs, Mathematical Proceedings of the Cambridge philosophical society, 95, 261-265, (1984) · Zbl 0551.05047
[30] Thomason, A., The extremal function for complete minors, Journal of combinatorial theory, series B, 81, 2, 318-338, (2001) · Zbl 1024.05083
[31] Wagner, K., Über eine eigenschaft der ebenen komplexe, Mathematische annalen, 114, 570-590, (1937) · JFM 63.0550.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.