Name
Abstract | ||
|---|---|---|
The Kneser graph KG(n,k) is the graph whose vertex set consists of all k-subsets of an 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 of a graph G is defined on the vertex set of G such that distinct vertices within distance two in G are joined by an edge. The span λ(G) of G is the smallest integer m such that an L(2,1)-labeling of G can be constructed using labels belonging to the set {0,1,…,m}. The following results are established. (1) χ(KG2(2k+1,k))⩽3k+2 for k⩾3 and χ(KG2(9,4))⩽12; (2) χ(SG2(2k+2,k))=λ(SG(2k+2,k))=2k+2 for k⩾4, χ(SG2(8,3))=8, λ(SG(8,3))=9, χ(SG2(6,2))=9, and λ(SG(6,2))=8. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.dam.2008.05.010 | Discrete Applied Mathematics |
Keywords | DocType | Volume |
Kneser graph,Schrijver graph,Chromatic number,L(2,1)-labeling,Graph square | Journal | 157 |
Issue | ISSN | Citations |
1 | 0166-218X | 3 |
PageRank | References | Authors |
0.42 | 4 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jun-yo Chen | 1 | 3 | 0.42 |
| Ko-wei Lih | 2 | 529 | 58.80 |
| Jiaojiao Wu | 3 | 109 | 9.33 |