Mathematics – Combinatorics
Scientific paper
2005-02-22
Mathematics
Combinatorics
22 pages. Main result given more generally. References and remarks added
Scientific paper
The local chromatic number of a graph G is the number of colors appearing in the most colorful closed neighborhood of a vertex minimized over all proper colorings of G. We show that two specific topological obstructions that have the same implications for the chromatic number have different implications for the local chromatic number. These two obstructions can be formulated in terms of the homomorphism complex Hom(K_2,G) and its suspension, respectively. These investigations follow the line of research initiated by Matousek and Ziegler who recognized a hierarchy of the different topological expressions that can serve as lower bounds for the chromatic number of a graph. Our results imply that the local chromatic number of 4-chromatic Kneser, Schrijver, Borsuk, and generalized Mycielski graphs is 4, and more generally, that 2r-chromatic versions of these graphs have local chromatic number at least r+2. This lower bound is tight in several cases by results in an earlier paper of the first two authors.
Simonyi Gabor
Tardos Gabor
Vrecica Sinisa T.
No associations
LandOfFree
Local chromatic number and distinguishing the strength of topological obstructions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Local chromatic number and distinguishing the strength of topological obstructions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Local chromatic number and distinguishing the strength of topological obstructions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-472122