Coloring the square of the Kneser graph KG ( 2 k + 1 , k ) and the Schrijver graph SG ( 2 k + 2 , k )
The Kneser graph  KG ( n , k ) is the graph whose vertex set consists of all k k -subsets of an n n -set, and two vertices are adjacent if and only if they are disjoint. The Schrijver graph  SG ( n , k ) is the subgraph of KG ( n , k ) induced by all vertices that are 2-stable subsets. The square G2 G 2 of a graph G G is defined on the vertex set of G G such that distinct vertices within distance two in G G are joined by an edge. The span ?(G) ? ( G ) of G G is the smallest integer m m such that an L(2,1) L ( 2 , 1 ) -labeling of G G can be constructed using labels belonging to the set {0,1,,m} { 0 , 1 ,  , m } . The following results are established. (1) ? ( KG 2 ( 2 k + 1 , k ) ) ? 3 k + 2 for k?3 k ? 3 and ? ( KG 2 ( 9 , 4 ) ) ? 12 ; (2) ? ( SG 2 ( 2 k + 2 , k ) ) = ? ( SG ( 2 k + 2 , k ) ) = 2 k + 2 for k?4 k ? 4 , ? ( SG 2 ( 8 , 3 ) ) = 8 , ? ( SG ( 8 , 3 ) ) = 9 , ? ( SG 2 ( 6 , 2 ) ) = 9 , and ? ( SG ( 6 , 2 ) ) = 8 .
kneser graph schrijver graph 1 ) chromatic number l(2 1) l ( 2 1 ) -labeling l(2 1 ) l(2 1 ) l ( 2 graph square