Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

 

Local chromatic number and distinguishing the strength of topological obstructions


Authors: Gábor Simonyi, Gábor Tardos and Sinisa T. Vrecica
Journal: Trans. Amer. Math. Soc. 361 (2009), 889-908
MSC (2000): Primary 05C15; Secondary 57M15.
Published electronically: August 15, 2008
MathSciNet review: 2452828
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: 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 $ {\rm Hom}(K_2,G)$ and its suspension, respectively.

These investigations follow the line of research initiated by Matoušek 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 of the first two authors.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 05C15, 57M15.

Retrieve articles in all journals with MSC (2000): 05C15, 57M15.


Additional Information

Gábor Simonyi
Affiliation: Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, 1364 Budapest, POB 127, Hungary
Email: simonyi@renyi.hu

Gábor Tardos
Affiliation: School of Computing Science, Simon Fraser University, Burnaby, British Columbia, Canada V5A 1S6 – and – Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, 1364 Budapest, POB 127, Hungary
Email: tardos@cs.sfu.ca

Sinisa T. Vrecica
Affiliation: Faculty of Mathematics, University of Belgrade, Studentski trg 16, P.O.B. 550, 11000 Belgrade, Serbia
Email: vrecica@matf.bg.ac.yu

DOI: http://dx.doi.org/10.1090/S0002-9947-08-04643-6
PII: S 0002-9947(08)04643-6
Keywords: Local chromatic number, box complex, Borsuk-Ulam theorem
Received by editor(s): February 22, 2005
Received by editor(s) in revised form: April 16, 2007
Published electronically: August 15, 2008
Additional Notes: The first author’s research was partially supported by the Hungarian Foundation for Scientific Research Grant (OTKA) Nos. T037846, T046376, AT048826, and NK62321
The second author’s research was partially supported by the NSERC grant 611470 and the Hungarian Foundation for Scientific Research Grant (OTKA) Nos. T037846, T046234, AT048826, and NK62321.
The third author’s research was supported by the Serbian Ministry of Science, Grant 144026.
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.