Paths of homomorphisms from stable Kneser graphs

DOI10.1007/S00493-013-2749-9MaRDI QIDQ485504zbMATH OpenOpenAlexFDO

Authors Carsten A. Schultz

Publication date 9 January 2015

Published in Combinatorica (Search for Journal in Brave)

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

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)

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.

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

Cites work

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

Cited in

(6)

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

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)