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).
Software:
PIGALEReferences:
| [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., (van Leeuwen, J., Graph Rewriting: An Algebraic and Logic Approach. Graph Rewriting: An Algebraic and Logic Approach, Handbook of Theoretical Computer Science, vol. 2 (1990), Elsevier: Elsevier Amsterdam), 142-193 · Zbl 0900.68282 |
| [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, (Enjalbert, P.; Mayr, E. W.; Wagner, K. W., Proceedings of the 11th Annual Symposium on Theoretical Aspects of Computer Science. Proceedings of the 11th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 775 (1994), Springer), 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, (Proc. 27th International Workshop on Graph-Theoretic Concepts in Computer Science. Proc. 27th International Workshop on Graph-Theoretic Concepts in Computer Science, WG ’01. Proc. 27th International Workshop on Graph-Theoretic Concepts in Computer Science. Proc. 27th International Workshop on Graph-Theoretic Concepts in Computer Science, WG ’01, Lecture Notes in Computer Science, vol. 2204 (2001)), 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); 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, (Aronov, B.; Basu, S.; Pach, J.; Sharir, M., The Goodman-Pollack Festschrift. The Goodman-Pollack Festschrift, Discrete & Computational Geometry: Algorithms and Combinatorics, vol. 25 (2003)), 651-664 · Zbl 1071.05526 |
| [17] | Nešetřil, J.; Ossona de Mendez, P., Aspects algorithmiques des classes d’expansion borne, (Esperet, L., 7e Journes Graphes et Algorithmes, vol. 1372-05 (2005), LaBRI - Universit Bordeaux I), 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); 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, (Raspaud, A.; Delmas, O., 7th International Colloquium on Graph Theory. 7th International Colloquium on Graph Theory, Electronic Notes in Discrete Mathematics, vol. 22 (2005), Elsevier), 101-106 · Zbl 1182.05102 |
| [21] | Nešetřil, J.; Ossona de Mendez, P., Linear time low tree-width partitions and algorithmic consequences, (Proceedings of the 38th Annual ACM Symposium on Theory of Computing. Proceedings of the 38th Annual ACM Symposium on Theory of Computing, STOC’06 (2006), ACM Press), 391-400 · Zbl 1301.05268 |
| [22] | Nešetřil, J.; Ossona de Mendez, P., Low tree-depth partitions of classes with bounded expansion, (Kra, J., Midsummer Combinatorial Workshop 2005 and DIMACS, DIMATIA, Rnyi Workshop 2005. Midsummer Combinatorial Workshop 2005 and DIMACS, DIMATIA, Rnyi Workshop 2005, KAM Series, vol. 2006-770 (2006)), 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, (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, Electronic Notes in Discrete Mathematics, vol. 28 (2007)), 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
