zbMATH — the first resource for mathematics

Tree-depth, subgraph coloring and homomorphism bounds. (English) Zbl 1089.05025
Summary: We define the notions tree-depth and upper chromatic number of a graph and show their relevance to local-global problems for graph partitions. In particular we show that the upper chromatic number coincides with the maximal function which can be locally demanded in a bounded coloring of any proper minor closed class of graphs. The rich interplay of these notions is applied to a solution of bounds of proper minor closed classes satisfying local conditions. In particular, we prove the following result: For every graph \(M\) and finite set \(\mathcal F\) of connected graphs there exists a (universal) graph \(U = U(M, \mathcal F)\in \mathrm{Forb}_{\mathrm h}(\mathcal F)\) such that any graph \(G \in \mathrm{Forb}_{\mathrm h}(\mathcal F)\) which does not have \(M\) as a minor satisfies \(G\rightarrow U\) (i.e. is homomorphic to \(U\)).
This solves the main open problem of restricted dualities for minor closed classes and as an application it yields the bounded chromatic number of exact odd powers of any graph in an arbitrary proper minor closed class. We also generalize the decomposition theorem of M. DeVos, G. Ding, B. Oporowski, D. P. Sanders, B. Reed, P. Seymour, and D. Vertigan [J. Comb. Theory, Ser. B 91; 25–41 (2004; Zbl 1042.05036)].

05C15 Coloring of graphs and hypergraphs
05C83 Graph minors
Full Text: DOI
[1] Alon, N.; McDiarmid, C.; Reed, B., Acyclic colouring of graphs, Random structures algorithms, 2, 277-288, (1991) · Zbl 0735.05036
[2] Alon, N.; McDiarmid, C.; Reed, B., Star arboricity, Combinatorica, 12, 375-380, (1992) · Zbl 0780.05043
[3] Alon, N.; Seymour, P.; Thomas, R., A separator theorem for nonplanar graphs, J. amer. math. soc., 3, 801-808, (1990) · Zbl 0747.05051
[4] Bodlaender, H.L.; Gilbert, J.R.; Hafsteinsson, H.; Kloks, T., Approximating tree-width, path-width, frontsize, and shortest elimination tree, J. algorithms, 18, 238-255, (1995) · Zbl 0818.68118
[5] Bollobás, B., Modern graph theory, (1997), Springer Verlag
[6] Borodin, O.V., On acyclic colorings of planar graphs, Discrete math., 25, 3, 211-236, (1979) · Zbl 0406.05031
[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.; Vertigan, D., Excluding any graph as a minor allows a low tree-width 2-coloring, J. combin. theory ser. B, 91, 25-41, (2004) · Zbl 1042.05036
[9] Dreyer, P.; Malon, Ch.; Nešetřil, J., Universal \(H\)-colourable graphs without a given configuration, Discrete math., 250, 245-252, (2002) · Zbl 1001.05060
[10] Häggkvist, R.; Hell, P., Universality of \(A\)-mote graphs, European J. combin., 23-27, (1993) · Zbl 0799.05063
[11] Hell, P.; Nešetřil, J., Graphs and homomorphisms, (2004), Oxford University Press · Zbl 1062.05139
[12] J. Hubička, J. Nešetřil, Universal partial order represented by means of trees and other simple graphs, in: ITI Series 2003-128, European J. Combin. 26 (5) 765-778
[13] Linial, N., Local – global phenomena in graphs, Combin. probab. comput., 2, 491-503, (1993) · Zbl 0803.68085
[14] Matoušek, J.; Nešetřil, J., Invitation to discrete mathematics, (1998), Oxford University Press · Zbl 0901.05001
[15] R. Naserasr, Homomorphisms and Edge Colorings of Planar Graphs (submitted for publication) · Zbl 1116.05032
[16] J. Nešetřil, P. Ossona de Mendez, Folding, J. Combin. Theory Ser. B (to appear)
[17] Nešetřil, J.; Ossona de Mendez, P., Colorings and homomorphisms of minor closed classes, (), 651-664 · Zbl 1071.05526
[18] J. Nešetřil, P. Ossona de Mendez, Cuts and bounds, Discrete Mathematics, ACCOTA (2003) (special issue) (in press)
[19] Nešetřil, J.; Shelah, S., Order of countable graphs, European J. combin., 24, 649-663, (2003) · Zbl 1030.03028
[20] Nešetřil, J.; Tardif, C., Duality theorems for finite structures (characterizing gaps and good characterizations), J. combin. theory ser. B, 80, 80-97, (2000) · Zbl 1024.05078
[21] Robertson, N.; Seymour, P.D., Graph minors II. algorithmic aspects of tree-width, J. algorithms, 7, 309-322, (1986) · Zbl 0611.05017
[22] P. Schaffer, Optimal node ranking of trees in linear time. Inform. Process. Lett. 33 (1989-1990) 91-96 · Zbl 0683.68038
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.