Local chromatic number and distinguishing the strength of topological obstructions
HTML articles powered by AMS MathViewer
- by Gábor Simonyi, Gábor Tardos and Siniša T. Vrećica PDF
- Trans. Amer. Math. Soc. 361 (2009), 889-908 Request permission
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 $\textrm {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
- Jan M. Aarts and Robbert J. Fokkink, Coincidence and the colouring of maps, Bull. London Math. Soc. 30 (1998), no. 1, 73–79. MR 1479039, DOI 10.1112/S0024609397003317
- N. Alon, P. Frankl, and L. Lovász, The chromatic number of Kneser hypergraphs, Trans. Amer. Math. Soc. 298 (1986), no. 1, 359–370. MR 857448, DOI 10.1090/S0002-9947-1986-0857448-8
- Dan Archdeacon, Joan Hutchinson, Atsuhiro Nakamoto, Seiya Negam, and Katsuhiro Ota, Chromatic numbers of quadrangulations on closed surfaces, J. Graph Theory 37 (2001), no. 2, 100–114. MR 1829924, DOI 10.1002/jgt.1005
- Eric Babson and Dmitry N. Kozlov, Complexes of graph homomorphisms, Israel J. Math. 152 (2006), 285–312. MR 2214465, DOI 10.1007/BF02771988
- Philip Bacon, Equivalent formulations of the Borsuk-Ulam theorem, Canadian J. Math. 18 (1966), 492–502. MR 195081, DOI 10.4153/CJM-1966-049-9
- I. Bárány, A short proof of Kneser’s conjecture, J. Combin. Theory Ser. A 25 (1978), no. 3, 325–326. MR 514626, DOI 10.1016/0097-3165(78)90023-7
- I. Bárány, personal communication.
- A. Björner, Topological methods, Handbook of combinatorics, Vol. 1, 2, Elsevier Sci. B. V., Amsterdam, 1995, pp. 1819–1872. MR 1373690
- Anders Björner and Mark De Longueville, Neighborhood complexes of stable Kneser graphs, Combinatorica 23 (2003), no. 1, 23–34. Paul Erdős and his mathematics (Budapest, 1999). MR 1996625, DOI 10.1007/s00493-003-0012-5
- Glen E. Bredon, Topology and geometry, Graduate Texts in Mathematics, vol. 139, Springer-Verlag, New York, 1993. MR 1224675, DOI 10.1007/978-1-4757-6848-0
- P. Csorba, Homotopy types of box complexes, Combinatorica, 27 (2007), no. 6, 669–682.
- Mark de Longueville, Bier spheres and barycentric subdivision, J. Combin. Theory Ser. A 105 (2004), no. 2, 355–357. MR 2046088, DOI 10.1016/j.jcta.2003.12.002
- P. Erdős, Graph theory and probability, Canadian J. Math. 11 (1959), 34–38. MR 102081, DOI 10.4153/CJM-1959-003-9
- P. Erdős, Z. Füredi, A. Hajnal, P. Komjáth, V. Rödl, and Á. Seress, Coloring graphs with locally few colors, Discrete Math. 59 (1986), no. 1-2, 21–34. MR 837951, DOI 10.1016/0012-365X(86)90065-8
- Ky Fan, A generalization of Tucker’s combinatorial lemma with topological applications, Ann. of Math. (2) 56 (1952), 431–437. MR 51506, DOI 10.2307/1969651
- Ky Fan, Evenly distributed subsets of $S^{n}$ and a combinatorial application, Pacific J. Math. 98 (1982), no. 2, 323–325. MR 650012, DOI 10.2140/pjm.1982.98.323
- L. Fehér, personal communication.
- Chris Godsil and Gordon Royle, Algebraic graph theory, Graduate Texts in Mathematics, vol. 207, Springer-Verlag, New York, 2001. MR 1829620, DOI 10.1007/978-1-4613-0163-9
- A. Gyárfás, T. Jensen, and M. Stiebitz, On graphs with strongly independent color-classes, J. Graph Theory 46 (2004), no. 1, 1–14. MR 2051464, DOI 10.1002/jgt.10165
- Allen Hatcher, Algebraic topology, Cambridge University Press, Cambridge, 2002. MR 1867354
- Marek Izydorek and Jan Jaworowski, Antipodal coincidence for maps of spheres into complexes, Proc. Amer. Math. Soc. 123 (1995), no. 6, 1947–1950. MR 1242089, DOI 10.1090/S0002-9939-1995-1242089-4
- J. Jaworowski, Existence of antipodal coincidence for maps of spheres, preprint.
- Jan Jaworowski, Periodic coincidence for maps of spheres, Kobe J. Math. 17 (2000), no. 1, 21–26. MR 1801262
- G. Kalai, personal communication.
- 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.
- János Körner, Concetta Pilotto, and Gábor Simonyi, Local chromatic number and Sperner capacity, J. Combin. Theory Ser. B 95 (2005), no. 1, 101–117. MR 2156342, DOI 10.1016/j.jctb.2005.03.006
- Igor Kříž, Equivariant cohomology and lower bounds for chromatic numbers, Trans. Amer. Math. Soc. 333 (1992), no. 2, 567–577. MR 1081939, DOI 10.1090/S0002-9947-1992-1081939-3
- L. Lovász, Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A 25 (1978), no. 3, 319–324. MR 514625, DOI 10.1016/0097-3165(78)90022-5
- L. Lovász, Self-dual polytopes and the chromatic number of distance graphs on the sphere, Acta Sci. Math. (Szeged) 45 (1983), no. 1-4, 317–323. MR 708798
- Jiří Matoušek, Using the Borsuk-Ulam theorem, Universitext, Springer-Verlag, Berlin, 2003. Lectures on topological methods in combinatorics and geometry; Written in cooperation with Anders Björner and Günter M. Ziegler. MR 1988723
- Jiří Matoušek and Günter M. Ziegler, Topological lower bounds for the chromatic number: a hierarchy, Jahresber. Deutsch. Math.-Verein. 106 (2004), no. 2, 71–90. MR 2073516
- Bojan Mohar and Paul D. Seymour, Coloring locally bipartite graphs on surfaces, J. Combin. Theory Ser. B 84 (2002), no. 2, 301–310. MR 1889261, DOI 10.1006/jctb.2001.2086
- B. Mohar, G. Simonyi, G. Tardos, On the local chromatic number of quadrangulations of surfaces, manuscript in preparation.
- E. V. Ščepin, A certain problem of L. A. Tumarkin, Dokl. Akad. Nauk SSSR 217 (1974), 42–43 (Russian). MR 0358764
- Edward R. Scheinerman and Daniel H. Ullman, Fractional graph theory, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1997. A rational approach to the theory of graphs; With a foreword by Claude Berge; A Wiley-Interscience Publication. MR 1481157
- A. Schrijver, Vertex-critical subgraphs of Kneser graphs, Nieuw Arch. Wisk. (3) 26 (1978), no. 3, 454–461. MR 512648
- D. Shkliarsky, On subdivisions of the two-dimensional sphere, Rec. Math. [Mat. Sbornik] N. S. 16(58) (1945), 125–128 (Russian, with English summary). MR 0013303
- Gábor Simonyi and Gábor Tardos, Local chromatic number, Ky Fan’s theorem and circular colorings, Combinatorica 26 (2006), no. 5, 587–626. MR 2279672, DOI 10.1007/s00493-006-0034-x
- Gábor Simonyi and Gábor Tardos, Colorful subgraphs in Kneser-like graphs, European J. Combin. 28 (2007), no. 8, 2188–2200. MR 2351519, DOI 10.1016/j.ejc.2007.04.015
- 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.
- M. Stiebitz, Beiträge zur Theorie der färbungskritischen Graphen, Habilitation, TH Ilmenau, 1985.
- Claude Tardif, Fractional chromatic numbers of cones over graphs, J. Graph Theory 38 (2001), no. 2, 87–94. MR 1857769, DOI 10.1002/jgt.1025
- A. W. Tucker, Some topological properties of disk and sphere, Proc. First Canadian Math. Congress, Montreal, 1945, University of Toronto Press, Toronto, 1946, pp. 285–309. MR 0020254
- James W. Walker, From graphs to ortholattices and equivariant maps, J. Combin. Theory Ser. B 35 (1983), no. 2, 171–192. MR 733022, DOI 10.1016/0095-8956(83)90070-9
- D. A. Youngs, $4$-chromatic projective graphs, J. Graph Theory 21 (1996), no. 2, 219–227. MR 1368748, DOI 10.1002/(SICI)1097-0118(199602)21:2<219::AID-JGT12>3.0.CO;2-E
- Rade T. Živaljević, WI-posets, graph complexes and ${\Bbb Z}_2$-equivalences, J. Combin. Theory Ser. A 111 (2005), no. 2, 204–223. MR 2156208, DOI 10.1016/j.jcta.2004.12.002
- R. T. Živaljević, personal communication.
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
- Siniša T. Vrećica
- Affiliation: Faculty of Mathematics, University of Belgrade, Studentski trg 16, P.O.B. 550, 11000 Belgrade, Serbia
- Email: vrecica@matf.bg.ac.yu
- 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. - © Copyright 2008
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - 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
- MathSciNet review: 2452828