The equivariant topology of stable Kneser graphs

The stable Kneser graph SG_n,k, n?1, k?0, introduced by Schrijver (1978) [19], is a vertex critical graph with chromatic number k+2, its vertices are certain subsets of a set of cardinality m=2n+k. Björner and de Longueville (2003) [5] have shown that its box complex is homotopy equivalent to a sphere, Hom(K₂,SG_n,k)?Sk. The dihedral group D2m acts canonically on SG_n,k, the group C₂ with 2 elements acts on K₂. We almost determine the (C₂×D2m)-homotopy type of Hom(K₂,SG_n,k) and use this to prove the following results.The graphs SG_2s,4 are homotopy test graphs, i.e. for every graph H and r?0 such that Hom(SG_2s,4,H) is (r−1)-connected, the chromatic number χ(H) is at least r+6.If k∉{0,1,2,4,8} and n?N(k) then SG_n,k is not a homotopy test graph, i.e. there are a graph G and an r?1 such that Hom(SG_n,k,G) is (r−1)-connected and χ(G)<r+k+2.     

Paths of homomorphisms from stable Kneser graphs

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≡3 (mod 4) and n≥2 we show that there is a component of the χ-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 χ(G)=χ(SG _n,k ) such that the complex Hom(SG _n,k ,G) is non-empty and connected. In particular, for k≡3 (mod 4) and n≥2 the graph SG _n,k is not a test graph.     

b-coloring of Kneser graphs

A $b$-coloring of a graph $G$ with $k$ colors is a proper coloring of $G$ using $k$ colors in which each color class contains a color dominating vertex, that is, a vertex which has a neighbor in each of the other color classes. The largest positive integer $k$ for which $G$ has a $b$-coloring using $k$ colors is the $b$-chromatic number $b\left(G\right)$ of $G$. The $b$-spectrum $S_b\left(G\right)$ of a graph $G$ is the set of positive integers $k,\chi \left(G\right)\le k\le b\left(G\right)$, for which $G$ has a $b$-coloring using $k$ colors. A graph $G$ is $b$-continuous if $S_b\left(G\right)$ = the closed interval $[\chi \left(G\right),b\left(G\right)]$. In this paper, we obtain an upper bound for the $b$-chromatic number of some families of Kneser graphs. In addition we establish that $[\chi \left(G\right),n+k+1]?S_b\left(G\right)$ for the Kneser graph $G=K(2n+k,n)$ whenever $3\le n\le k+1$. We also establish the $b$-continuity of some families of regular graphs which include the family of odd graphs.     

Local coloring of Kneser graphs

A local coloring of a graph G is a function c:V(G)→N having the property that for each set S⊆V(G) with 2≤|S|≤3, there exist vertices u,v∈S such that |c(u)−c(v)|≥m_S, where m_S is the number of edges of the induced subgraph 〈S〉. The maximum color assigned by a local coloring c to a vertex of G is called the value of c and is denoted by χ_?(c). The local chromatic number of G is χ_?(G)=min{χ_?(c)}, where the minimum is taken over all local colorings c of G. The local coloring of graphs was introduced by Chartrand et al. [G. Chartrand, E. Salehi, P. Zhang, On local colorings of graphs, Congressus Numerantium 163 (2003) 207-221]. In this paper the local coloring of Kneser graphs is studied and the local chromatic number of the Kneser graph K(n,k) for some values of n and k is determined.     

On the diameter of generalized Kneser graphs

Let r, k be positive integers, s(<r), a nonnegative integer, and n=2r-s+k. The set of r-subsets of [n]={1,2,…,n} is denoted by [n]^r. The generalized Kneser graph K(n,r,s) is the graph whose vertex-set is [n]^r where two r-subsets A and B are joined by an edge if |A∩B|?s. This note determines the diameter of generalized Kneser graphs. More precisely, the diameter of K(n,r,s) is equal to , which generalizes a result of Valencia-Pabon and Vera [On the diameter of Kneser graphs, Discrete Math. 305 (2005) 383-385].     

On the b-chromatic number of Kneser graphs

In this note, we prove that for any integer n≥3 the b-chromatic number of the Kneser graph KG(m,n) is greater than or equal to . This gives an affirmative answer to a conjecture of [6].     

Extremal problems concerning Kneser graphs

Let and be two intersecting families of k-subsets of an n-element set. It is proven that | | ≤ (_k−1ⁿ⁻¹) + (_k−1ⁿ⁻¹) holds for , and equality holds only if there exist two points a, b such that {a, b} ∩ F ≠ for all F . For an example showing that in this case max | | = (1−o(1))(_kⁿ) is given. This disproves an old conjecture of Erdös [7]. In the second part we deal with several generalizations of Kneser's conjecture.     

Maximum bipartite subgraphs of Kneser graphs

We investigate the maximum number of edges in a bipartite subgraph of the Kneser graphK(n, r). The exact solution is given for eitherr arbitrary andn (4.3 + o(1))r, orr = 2 andn arbitrary. The problem is in connection with the study of the bipartite subgraph polytope of a graph.Research supported in part by the AKA Research Fund of the Hungarian Academy of Sciences     

On finite simple groups and Kneser graphs

For a finite group G let Γ(G) be the (simple) graph defined on the elements of G with an edge between two (distinct) vertices if and only if they generate G. The chromatic number of Γ(G) is considered for various non-solvable groups G.     

Resolving sets for Johnson and Kneser graphs

A set of vertices S$S$ in a graph G$G$ is a resolving set   for G$G$ if, for any two vertices u,v$u,v$, there exists x∈S$x\in S$ such that the distances d(u,x)≠d(v,x)$d(u,x)\ne d(v,x)$. In this paper, we consider the Johnson graphs J(n,k)$J(n,k)$ and Kneser graphs K(n,k)$K(n,k)$, and obtain various constructions of resolving sets for these graphs. As well as general constructions, we show that various interesting combinatorial objects can be used to obtain resolving sets in these graphs, including (for Johnson graphs) projective planes and symmetric designs, as well as (for Kneser graphs) partial geometries, Hadamard matrices, Steiner systems and toroidal grids.     

On the locating chromatic number of Kneser graphs

Let c be a proper k-coloring of a connected graph G and Π=(C₁,C₂,…,C_k) be an ordered partition of V(G) into the resulting color classes. For a vertex v of G, the color code of v with respect to Π is defined to be the ordered k-tuple c_Π(v):=(d(v,C₁),d(v,C₂),…,d(v,C_k)), where d(v,C_i)=min{d(v,x)|x∈C_i},1≤i≤k. If distinct vertices have distinct color codes, then c is called a locating coloring. The minimum number of colors needed in a locating coloring of G is the locating chromatic number of G, denoted by χ_L(G). In this paper, we study the locating chromatic number of Kneser graphs. First, among some other results, we show that χ_L(KG(n,2))=n−1 for all n≥5. Then, we prove that χ_L(KG(n,k))≤n−1, when n≥k². Moreover, we present some bounds for the locating chromatic number of odd graphs.     

Independence number of products of Kneser graphs

We study the independence number of a product of Kneser graph $K(n,k)$ with itself, where we consider all four standard graph products. The cases of the direct, the lexicographic and the strong product of Kneser graphs are not difficult (the formula for $\alpha (K(n,k)⊠K(n,k))$ is presented in this paper), while the case of the Cartesian product of Kneser graphs is much more involved. We establish a lower bound and an upper bound for the independence number of $K(n,2)\square K(n,2)$, which are asymptotically tending to $n^3∕3$ and $3n^3∕8$, respectively. The former is obtained by a construction, which differs from the standard diagonalization procedure, while for the upper bound the $\ell$-independence number of Kneser graphs can be applied. We also establish some constructions in odd graphs $K(2k+1,k)$, which give a lower bound for the 2-independence number of these graphs, and prove that two such constructions give the same lower bound as a previously known one. Finally, we consider the $s$-stable Kneser graphs $K{(ks+1,k)}_{s-stab}$, derive a formula for their $\ell$-independence number, and give the exact value of the independence number of the Cartesian square of $K{(ks+1,k)}_{s-stab}$.     

A new coloring theorem of Kneser graphs

In 1997, Johnson, Holroyd and Stahl conjectured that the circular chromatic number of the Kneser graphs KG(n,k) is equal to the chromatic number of these graphs. This was proved by Simonyi and Tardos (2006) [13] and independently by Meunier (2005) [10], if χ(KG(n,k)) is even. In this paper, we propose an alternative version of Kneser's coloring theorem to confirm the Johnson-Holroyd-Stahl conjecture.     

Long induced paths and cycles in Kneser graphs

We present some lower and upper bounds on the length of the maximum induced paths and cycles in Kneser graphs.     

Clique number of Xor products of Kneser graphs

In this article we investigate a problem in graph theory, which has an equivalent reformulation in extremal set theory similar to the problems researched in “A general 2-part Erd?s-Ko-Rado theorem” by Gyula O.H. Katona, who proposed our problem as well. In the graph theoretic form we examine the clique number of the Xor product of two isomorphic $KG(N,k)$ Kneser graphs. Denote this number with $f(k,N)$. We give lower and upper bounds on $f(k,N)$, and we solve the problem up to a constant deviation depending only on k, and find the exact value for $f(2,N)$ if N is large enough. Also we compute that $f(k,k^2)$ is asymptotically equivalent to $k^2$.     

On random subgraphs of Kneser graphs and their generalizations

A series of results are obtained on the stability of the independence number of random subgraphs of distance graphs, which are natural generalizations of the classical Kneser graphs.