Tree-depth, subgraph coloring and homomorphism bounds

摘要: We define the notions tree-depth and upper chromatic number of a graph show their relevance to local-global problems for partitions. In particular we that coincides with maximal function which can be locally demanded in bounded coloring any proper minor closed class graphs. The rich interplay these is applied solution bounds classes satisfying local conditions. particular, prove following result:For every M finite set F connected graphs there exists (universal) U = U(M, F) ∈ Forbh(F) such G does not have as satisfies → (i.e. homomorphic U).This solves main open problem restricted dualities an application it yields exact odd powers arbitrary class. also generalize decomposition theorem DeVos et al. [M. DeVos, G. Ding, B. Oporowski, D.P. Sanders, Reed, P. Seymour, D. Vertigan, Excluding allows low tree-width 2-coloring, J. Combin. Theory Ser. B 91 (2004) 25-41].