Connectedness of certain graph coloring complexes. (English) Zbl 07890718
Summary: In this article, we consider the bipartite graphs \(K_2 \times K_n\). We prove that the connectedness of the complex \(\mathrm{Hom}( K_2 \times K_n, K_m)\) is \(m - n - 1\) if \(m \geq n\) and \(m - 3\) in all the other cases. Therefore, we show that for this class of graphs, \( \mathrm{Hom}(G, K_m)\) is exactly \((m - d - 2)\)-connected, \(m \geq n\), where \(d\) is the maximal degree of the graph \(G\).
MSC:
| 57M15 | Relations of low-dimensional topology with graph theory |
| 55U05 | Abstract complexes in algebraic topology |
| 05C15 | Coloring of graphs and hypergraphs |
| 05E45 | Combinatorial aspects of simplicial complexes |
| 57Q70 | Discrete Morse theory and related ideas in manifold topology |
References:
| [1] | Babson, Eric; Kozlov, Dmitry N., Complexes of graph homomorphisms, Isr. J. Math., 152, 285-312, 2006 · Zbl 1205.52009 |
| [2] | Babson, Eric; Kozlov, Dmitry N., Proof of the Lovaśz conjecture, Ann. Math., 165, 965-1007, 2007 · Zbl 1132.05019 |
| [3] | Benedetti, Bruno, Discrete Morse theory for manifolds with boundary, Trans. Am. Math. Soc., 364, 12, 6631-6670, 2012 · Zbl 1288.57022 |
| [4] | Björner, Anders, Topological methods, (Handbook of Combinatorics, Vol. 1, 2, 1996, Elsevier: Elsevier Amsterdam), 1819-1872, 1995 · Zbl 0851.52016 |
| [5] | Čukić, Sonja; Kozlov, Dimitry, Higher connectivity of graph coloring complexes, Int. Math. Res. Not., 25, 1543-1562, 2005 · Zbl 1077.05038 |
| [6] | Dochtermann, Anton, Hom complexes and homotopy type in the category of graphs, Eur. J. Comb., 30, 490-509, 2009 · Zbl 1167.05017 |
| [7] | Dochtermann, Anton; Schultz, Carsten, Topology of Hom complexes and test graphs for bounding chromatic number, Isr. J. Math., 187, 371-417, 2012 · Zbl 1292.05090 |
| [8] | Forman, Robin, Morse theory for cell complexes, Adv. Math., 134, 1, 90-145, 1998 · Zbl 0896.57023 |
| [9] | Godsil, Chris; Royle, Gordon, Algebraic Graph Theory, Graduate Texts in Mathematics, 207, 2001, Springer Verlag: Springer Verlag New York · Zbl 0968.05002 |
| [10] | Green, Richard M.; Harper, Jacob T., Morse matchings on polytopes, Algebraic Geom. Topol., 12, 4, 2429-2450, 2013 · Zbl 1261.05128 |
| [11] | Hatcher, Allen, Algebraic Topology, 2002, Cambridge University Press · Zbl 1044.55001 |
| [12] | Hoory, Shlomo; Linial, Nathan, A counterexample to a conjecture of Björner and Lovász on the χ-coloring complex, J. Comb. Theory, Ser. B, 95, 2, 346-349, 2005 · Zbl 1075.05036 |
| [13] | Hell, Pavol; Nešetr̆il, Jaroslav, Graphs and Homomorphisms, Oxford Lecture Series in Mathematics and Its Applications, vol. 28, 2004, Oxford University Press: Oxford University Press Oxford · Zbl 1062.05139 |
| [14] | Jonsson, Jakob, Simplicial Complexes of Graphs, Lecture Notes in Mathematics, 1928, 2008, Springer Verlag: Springer Verlag Berlin |
| [15] | Kneser, M., Aufgabe 300, Jber. Deutsch. Math.-Verein., 58, 1955 |
| [16] | Kozlov, Dmitry, A simple proof for folds on both sides in complexes of graph homomorphisms, Proc. Am. Math. Soc., 134, 5, 1265-1270, 2006 · Zbl 1081.05035 |
| [17] | Kozlov, Dmitry, Chromatic numbers, morphism complexes and Steifel Whitney Classes, (Geometric Combinatorics. Geometric Combinatorics, IAS Park City Math. Ser., vol. 13, 2007, Amer. Math. Soc.), 249-315 · Zbl 1139.05022 |
| [18] | Kozlov, Dmitry, Cohomology of colorings of cycles, Am. J. Math., 130, 829-857, 2008 · Zbl 1198.05062 |
| [19] | Kozlov, Dmitry, Combinatorial Algebraic Topology, 1928, 2008, Springer Verlag: Springer Verlag Berlin |
| [20] | Lewiner, Thomas; Lopes, Helio; Tavares, Geovan, Applications of Forman’s discrete Morse theory to topology visualization and mesh compression, IEEE Trans. Vis. Comput. Graph., 10, 5, 499-508, 2004 |
| [21] | Lovász, László, Kneser’s conjecture, chromatic number and homotopy, J. Comb. Theory, Ser. A, 25, 319-324, 1978 · Zbl 0418.05028 |
| [22] | Maclane, Saunders, Categories for the Working Mathematician, Graduate Texts in Mathematics, vol. 5, 1998, Springer-Verlag: Springer-Verlag New York · Zbl 0906.18001 |
| [23] | Malen, Greg, Homomorphism complexes and k-cores, Discrete Math., 341, 9, 2567-2574, 2018 · Zbl 1392.05056 |
| [24] | Matsushita, Takahiro, Answers to some problems about graph coloring test graphs, Eur. J. Comb., 45, 59-64, 2015 · Zbl 1304.05051 |
| [25] | Nilakantan, Nandini; Shukla, Samir, Neighborhood complexes of some exponential graphs electron, J. Combin., 23, 2, Article 2.26 pp., 2016 · Zbl 1336.05045 |
| [26] | Schultz, Carsten, The equivariant topology of stable Kneser graphs, J. Comb. Theory, Ser. A, 118, 8, 2291-2318, 2011 · Zbl 1245.05052 |
| [27] | Shukla, Samir, Neighborhood complexes, homotopy test graphs and an application to coloring of product graphs, Graphs Comb., 38, 3, 1-14, 2022 · Zbl 1490.05085 |
| [28] | Vassiliev, Victor A., Complexes of connected graphs, (The Gelfand Mathematical Seminars, 1993, Birkhäuser: Birkhäuser Boston), 1990-1992 · Zbl 0812.55005 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
