Remote Access Transactions of the American Mathematical Society
Green Open Access

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.
DOI: https://doi.org/10.1090/S0002-9947-08-04643-6
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?)

  • 1. J. M. Aarts, R. J. Fokkink, Coincidence and the colouring of maps, Bull. London Math. Soc., 30 (1998), no. 1, 73-79. MR 1479039 (98j:55002)
  • 2. N. Alon, P. Frankl, L. Lovász, The chromatic number of Kneser hypergraphs, Trans. Amer. Math. Soc., 298 (1986), 359-370. MR 857448 (88g:05098)
  • 3. D. Archdeacon, J. Hutchinson, A. Nakamoto, S. Negami, K. Ota, Chromatic numbers of quadrangulations on closed surfaces, J. Graph Theory, 37 (2001), no. 2, 100-114. MR 1829924 (2002j:05044)
  • 4. E. Babson, D.N. Kozlov, Complexes of graph homomorphisms, Israel J. Math., 152 (2006), 285-312. MR 2214465 (2007b:52024)
  • 5. P. Bacon, Equivalent formulations of the Borsuk-Ulam theorem, Canad. J. Math., 18 (1966), 492-502. MR 0195081 (33:3286)
  • 6. I. Bárány, A short proof of Kneser's conjecture J. Combin. Theory Ser. A, 25 (1978), no. 3, 325-326. MR 514626 (81g:05056)
  • 7. I. Bárány, personal communication.
  • 8. A. Björner, Topological methods, in: Handbook of Combinatorics (Graham, Grötschel, Lovász eds.), 1819-1872, Elsevier, Amsterdam, 1995. MR 1373690 (96m:52012)
  • 9. A. Björner, M. de Longueville, Neighborhood complexes of stable Kneser graphs, Combinatorica, 23 (2003), no. 1, 23-34. MR 1996625 (2004e:05072)
  • 10. G. Bredon, Topology and Geometry, Graduate Texts in Mathematics 139, Springer-Verlag, New York, 1993. MR 1224675 (94d:55001)
  • 11. P. Csorba, Homotopy types of box complexes, Combinatorica, 27 (2007), no. 6, 669-682.
  • 12. M. de Longueville, Bier spheres and barycentric subdivision, J. Combin. Theory Ser. A, 105 (2004), 355-357. MR 2046088 (2005d:52016)
  • 13. P. Erdős, Graph theory and probability, Canad. J. Math., 11 (1959), 34-38. MR 0102081 (21:876)
  • 14. P. Erdős, Z. Füredi, A. Hajnal, P. Komjáth, V. Rödl, Á. Seress, Coloring graphs with locally few colors, Discrete Math., 59 (1986), 21-34. MR 837951 (87f:05069)
  • 15. K. Fan, A generalization of Tucker's combinatorial lemma with topological applications, Annals of Mathematics, 56 (1952), no. 2, 431-437. MR 0051506 (14:490c)
  • 16. K. Fan, Evenly distributed subsets of $ \mathbb{S}^n$ and a combinatorial application, Pacific J. Math., 98 (1982), no. 2, 323-325. MR 650012 (84c:54070)
  • 17. L. Fehér, personal communication.
  • 18. C. Godsil, G. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics 207, Springer-Verlag, New York, 2001. MR 1829620 (2002f:05002)
  • 19. A. Gyárfás, T. Jensen, M. Stiebitz, On graphs with strongly independent colour-classes, J. Graph Theory, 46 (2004), 1-14. MR 2051464 (2005e:05047)
  • 20. A. Hatcher, Algebraic Topology, Cambridge University Press, 2002. Electronic version available at http://www.math.cornell.edu/˜hatcher/AT/ATpage.html. MR 1867354 (2002k:55001)
  • 21. M. Izydorek, J. Jaworowski, Antipodal coincidence for maps of spheres into complexes, Proc. Amer. Math. Soc., 123 (1995), 1947-1950. MR 1242089 (96c:55002)
  • 22. J. Jaworowski, Existence of antipodal coincidence for maps of spheres, preprint.
  • 23. J. Jaworowski, Periodic coincidence for maps of spheres, Kobe J. Math., 17 (2000), no. 1, 21-26. MR 1801262 (2001k:55007)
  • 24. G. Kalai, personal communication.
  • 25. D. N. Kozlov, Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes. Geometric Combinatorics, 249-315 (E. Miller, V. Reiner, B. Sturmfels eds.) IAS/Park City Mathematics Series 13, American Mathematical Society, Providence, RI; Institute for Advanced Study (IAS), Princeton, NJ, 2007.
  • 26. J. Körner, C. Pilotto, G. Simonyi, Local chromatic number and Sperner capacity, J. Combin. Theory, Ser B., 95 (2005), 101-117. MR 2156342 (2006c:05058)
  • 27. I. Křıž, Equivariant cohomology and lower bounds for chromatic numbers, Trans. Amer. Math. Soc., 333 (1992), no. 2, 567-577; I. Křıž, A correction to: ``Equivariant cohomology and lower bounds for chromatic numbers'', Trans. Amer. Math. Soc., 352 (2000), no. 4, 1951-1952. MR 1081939 (92m:05085)
  • 28. L. Lovász, Kneser's conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A, 25 (1978), no. 3, 319-324. MR 514625 (81g:05059)
  • 29. L. Lovász, Self-dual polytopes and the chromatic number of distance graphs on the sphere, Acta Sci. Math. (Szeged), 45 (1983), 317-323. MR 708798 (84i:05051)
  • 30. J. Matoušek, Using the Borsuk-Ulam Theorem. Lectures on Topological Methods in Combinatorics and Geometry, Springer-Verlag, Berlin, 2003. MR 1988723 (2004i:55001)
  • 31. J. Matoušek, G.M. Ziegler, Topological lower bounds for the chromatic number: A hierarchy, Jahresber. Deutsch. Math.-Verein., 106 (2004), no. 2, 71-90. MR 2073516 (2005d:05067)
  • 32. B. Mohar, P.D. Seymour, Coloring locally bipartite graphs on surfaces, J. Combin. Theory Ser. B, 84 (2002), no. 2, 301-310. MR 1889261 (2003b:05059)
  • 33. B. Mohar, G. Simonyi, G. Tardos, On the local chromatic number of quadrangulations of surfaces, manuscript in preparation.
  • 34. E. V. Ščepin, A certain problem of L. A. Tumarkin. (Russian) Dokl. Akad. Nauk SSSR, 217 (1974), 42-43; English translation: Soviet Math. Dokl., 15 (1974), no. 4, 1024-1026 (1975). MR 0358764 (50:11223)
  • 35. E.R. Scheinerman, D.H. Ullman, Fractional Graph Theory, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley and Sons, Chichester, 1997. MR 1481157 (98m:05001)
  • 36. A. Schrijver, Vertex-critical subgraphs of Kneser graphs, Nieuw Arch. Wisk. (3), 26 (1978), no. 3, 454-461. MR 512648 (80g:05037)
  • 37. D. Shkliarsky, On subdivisions of the two-dimensional sphere. (Russian. English summary) Rec. Math. [Mat. Sbornik] N. S. 16(58), (1945), 125-128. MR 0013303 (7:136d)
  • 38. G. Simonyi, G. Tardos, Local chromatic number, Ky Fan's theorem, and circular colorings, Combinatorica, 26 (2006), 587-626. MR 2279672 (2007j:05083)
  • 39. G. Simonyi, G. Tardos, Colorful subgraphs in Kneser-like graphs, European J. Combin., 28 (2007), no. 8, 2188-2200. MR 2351519
  • 40. G. Simonyi, G. Tardos, Local chromatic number and topological properties of graphs, DMTCS Proceedings Series, AE (2005), Proceedings of the European Conference on Combinatorics, Graph Theory and Applications, 375-378.
  • 41. M. Stiebitz, Beiträge zur Theorie der färbungskritischen Graphen, Habilitation, TH Ilmenau, 1985.
  • 42. C. Tardif, Fractional chromatic numbers of cones over graphs, J. Graph Theory, 38 (2001), 87-94. MR 1857769 (2002g:05090)
  • 43. A. W. Tucker, Some topological properties of disk and sphere, Proc. First Canadian Math. Congress, Montreal, 1945, University of Toronto Press, Toronto, 1946, 285-309. MR 0020254 (8:525g)
  • 44. J. W. Walker, From graphs to ortholattices and equivariant maps, J. Combin. Theory Ser. B, 35 (1983), 171-192. MR 733022 (86a:05050)
  • 45. D.A. Youngs, $ 4$-chromatic projective graphs, J. Graph Theory, 21 (1996), 219-227. MR 1368748 (96h:05081)
  • 46. R.T. Živaljević, $ WI$-posets, graph complexes and $ \mathbb{Z}_2$-equivalences, J. Combin. Theory Ser. A, 111 (2005), no. 2, 204-223. MR 2156208 (2006e:05191)
  • 47. R.T. Živaljević, personal communication.

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: https://doi.org/10.1090/S0002-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.

American Mathematical Society