Paths of homomorphisms from stable Kneser graphs

DOI10.1007/S00493-013-2749-9zbMATH Open1313.05071arXiv1006.0474OpenAlexW2091829352MaRDI QIDQ485504FDOQ485504

Authors: Carsten A. Schultz 

Publication date: 9 January 2015

Published in: Combinatorica (Search for Journal in Brave)

Abstract: We denote by SG_{n,k} the stable Kneser graph (Schrijver graph) of stable n-subsets of a set of cardinality 2n+k. For k congruent 3 (mod 4) and nge2 we show that there is a component of the chi-colouring graph of SG_{n,k} which is invariant under the action of the automorphism group of SG_{n,k}. We derive that there is a graph G with chi(G)=chi(SG_{n,k}) such that the complex Hom(SG_{n,k}, G) is non-empty and connected. In particular, for k congruent 3 (mod 4) and nge2 the graph SG_{n,k} is not a test graph.

Full work available at URL: https://arxiv.org/abs/1006.0474

Recommendations

• The equivariant topology of stable Kneser graphs
• The equivariant topology of stable Kneser graphs
• Independence complexes of stable Kneser graphs
• The neighborhood complexes of almost \(s\)-stable Kneser graphs
• On the neighborhood complex of \(\overrightarrow{s} \)-stable Kneser graphs

zbMATH Keywords

Kneser graphSchrijver graphtest graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Kneser's conjecture, chromatic number, and homotopy
• A short proof of Kneser's conjecture
• Title not available (Why is that?)
• Hom complexes and homotopy theory in the category of graphs
• Complexes of graph homomorphisms
• Proof of the Lovász conjecture
• The universality of Hom complexes of graphs
• Topology of Hom complexes and test graphs for bounding chromatic number
• Graph colorings, spaces of edges and spaces of circuits
• Neighborhood complexes of stable Kneser graphs
• The homotopy type of complexes of graph homomorphisms between cycles
• A counterexample to a conjecture of Björner and Lovász on the \(\chi\)-coloring complex
• The equivariant topology of stable Kneser graphs
• Symmetries of the stable Kneser graphs

Cited In (6)

• A special case of the stahl conjecture
• Answers to some problems about graph coloring test graphs
• The equivariant topology of stable Kneser graphs
• The equivariant topology of stable Kneser graphs
• A topological lower bound for the chromatic number of a special family of graphs
• Shifts of the stable Kneser graphs and hom-idempotence

This page was built for publication: Paths of homomorphisms from stable Kneser graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q485504)