Homotopy type of neighborhood complexes of Kneser graphs, \(KG_{2,k}\). (English) Zbl 1401.05125
Summary: A. Schrijver [Nieuw Arch. Wiskd., III. Ser. 26, 454–461 (1978; Zbl 0432.05026)] identified a family of vertex critical subgraphs of the Kneser graphs called the stable Kneser graphs \(SG_{n,k}\). A. Björner and M. de Longueville [Combinatorica 23, No. 1, 23–34 (2003; Zbl 1047.05015)] proved that the neighborhood complex of the stable Kneser graph \(SG_{n,k}\) is homotopy equivalent to a \(k\)-sphere. In this article, we prove that the homotopy type of the neighborhood complex of the Kneser graph \(KG_{2,k}\) is a wedge of \((k+4)(k+1)+1\) spheres of dimension \(k\). We construct a maximal subgraph \(S_{2,k}\) of \(KG_{2,k}\), whose neighborhood complex is homotopy equivalent to the neighborhood complex of \(SG_{2,k}\). Further, we prove that the neighborhood complex of \(S_{2,k}\) deformation retracts onto the neighborhood complex of \(SG_{2,k}\).
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 57M15 | Relations of low-dimensional topology with graph theory |
Online Encyclopedia of Integer Sequences:
Number of wedged n-spheres in the homotopy type of the neighborhood complex of Kneser graph KG_{3,n}.References:
| [1] | Björner, A.; Longueville, M., Neighborhood complexes of stable Kneser graphs, Combinatorica, 23, 23-34, (2003) · Zbl 1047.05015 · doi:10.1007/s00493-003-0012-5 |
| [2] | Braun B, Independence complexes of stable Kneser graphs, Electronic J. Combinatorics, 18(1) (2011) · Zbl 1217.05174 |
| [3] | Braun, B.; Zeckner, M., Deformation ratracts of neighborhood complexes of stable Kneser graphs, Proc. Amer. Math. Soc., 142, 413-427, (2014) · Zbl 1282.05227 · doi:10.1090/S0002-9939-2013-11803-4 |
| [4] | Forman, R., Morse theory for cell complexes, Advances in Mathematics, 134, 90-145, (1998) · Zbl 0896.57023 · doi:10.1006/aima.1997.1650 |
| [5] | Jonsson J, Simplicial complexes of graphs, Vol. 1928 of Lecture Notes in Mathematics (2008) (Berlin: Springer-Verlag) · Zbl 1152.05001 |
| [6] | Kozlov D, Combinatorial algebraic topology, Algorithhms and Computation in Mathematics, vol. 21 (2007) (Springer Science & Business Media) |
| [7] | Lovász, L., Kneser’s conjecture, chromatic number, and homotopy, J. Combinatorial Theory Series A, 25, 319-324, (1978) · Zbl 0418.05028 · doi:10.1016/0097-3165(78)90022-5 |
| [8] | Schrijver, A., Vertex-critical subgraphs of Kneser graphs, Nieuw Archief voor Wiskunde, 26, 454-461, (1978) · Zbl 0432.05026 |
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.
