Results 1 to 10 of about 65 (53)
The equivariant topology of stable Kneser graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2011 Schrijver introduced the stable Kneser graph $SG_{n,k}, n \geq 1, k \geq 0$. This graph is a vertex critical graph with chromatic number $k+2$, its vertices are certain subsets of a set of cardinality $m=2n+k$.
Carsten Schultz
doaj +6 more sources
The automorphism group of the s-stable Kneser graphs
Advances in Applied Mathematics, 2017 For $k,s\geq2$, the $s$-stable Kneser graphs are the graphs with vertex set the $k$-subsets $S$ of $\{1,\ldots,n\}$ such that the circular distance between any two elements in $S$ is at least $s$ and two vertices are adjacent if and only if the corresponding $k$-subset are disjoint.
Pablo Torres
exaly +7 more sources
Shifts of the stable Kneser graphs and hom-idempotence
European Journal of Combinatorics, 2017 A graph $G$ is said to be {\em hom-idempotent} if there is a homomorphism from $G^2$ to $G$, and {\em weakly hom-idempotent} if for some $n \geq 1$ there is a homomorphism from $G^{n+1}$ to $G^n$. Larose et al. [{\em Eur. J. Comb. 19:867-881, 1998}] proved that Kneser graphs $\operatorname{KG}(n,k)$ are not weakly hom-idempotent for $n \geq 2k+1$, $k ...
Mario Valencia-Pabon, Pablo Torres
exaly +6 more sources
Stable sets of maximal size in Kneser-type graphs
European Journal of Combinatorics, 2004 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Claudia Malvenuto, Benoit Larose
exaly +2 more sources
Symmetries of the stable Kneser graphs
Advances in Applied Mathematics, 2010 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
exaly +3 more sources
Independence Complexes of Stable Kneser Graphs [PDF]
The Electronic Journal of Combinatorics, 2011 For integers $n\geq 1$, $k\geq 0$, the stable Kneser graph $SG_{n,k}$ (also called the Schrijver graph) has as vertex set the stable $n$-subsets of $[2n+k]$ and as edges disjoint pairs of $n$-subsets, where a stable $n$-subset is one that does not contain any $2$-subset of the form $\{i,i+1\}$ or $\{1,2n+k\}$.
openaire +7 more sources
Deformation retracts of neighborhood complexes of stable Kneser graphs [PDF]
Proceedings of the American Mathematical Society, 2013 In 2003, A. Bjorner and M. de Longueville proved that the neighborhood complex of the stable Kneser graph SG_{n,k} is homotopy equivalent to a k-sphere. Further, for n=2 they showed that the neighborhood complex deformation retracts to a subcomplex isomorphic to the associahedron.
Braun, Benjamin, Zeckner, Matthew
openaire +2 more sources
A study of the neighborhood complex of $-stable Kneser graphs
Gradus, 2021 In 1978, Alexander Schrijver defined the stable Kneser graphs as a vertex critical subgraphs of the Kneser graphs. In the early 2000s, Günter M. Ziegler generalized Schrijver’s construction and defined the s-stable Kneser graphs. Thereafter Frédéric Meunier determined the chromatic number of the s-stable Kneser graphs for special cases and formulated a
openaire +2 more sources
Maximum stable sets in analogs of Kneser and complete graphs
European Journal of Combinatorics, 2009 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Gábor Kun, Benoît Larose
openaire +2 more sources
Studying the multichromatic number of the almost s-stable Kneser graphs
Gradus, 2022 In the early 1970’s Gilbert introduced n-tuple colorings of graphs motivated by practical problems. After this Saul Stahl studied the properties of these colorings and formulated the conjecture on the multichromatic number of the Kneser graphs. Motivated by Stahl’s conjecture we will investigate the multichromatic number of the almost s-stable Kneser ...
openaire +2 more sources