Tree depth, subgraph coloring and homomorphism bounds (2004).

Content Provider	CiteSeerX
Author	Nesetril, Jaroslav Mendez, Patrice Ossona De
Abstract	We define the notions tree depth and upper chromatic number of a graph and show their relevance to local - global problems for graphs partitions. Particularly 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 minor closed classes satisfying local conditions. This solves an open problem and as an application it yields the bounded chromatic number of exact odd powers of any graph in an arbitrary proper minor closed class.
File Format	PDF
Publisher Date	2004-01-01
Access Restriction	Open
Subject Keyword	Subgraph Coloring Tree Depth Homomorphism Bound Graph Partition Bounded Coloring Local Global Problem Arbitrary Proper Minor Open Problem Bounded Chromatic Number Rich Interplay Proper Minor Upper Chromatic Number Maximal Function Local Condition Exact Odd Power Upper Chromatic Number Coincides
Content Type	Text