Local chromatic number and distinguishing the strength of topological obstructions

Simonyi, Gábor; Tardos, Gábor; Vrećica, Siniša

doi:10.1090/S0002-9947-08-04643-6

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.