Browsing by Subject "$L(2,1)$-labeling"

The emph {Kneser graph} ${sf 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 emph{square} $G^2$ of a graph $G$ is the graph defined on the vertex set of $G$ such that distinct vertices within distance two in $G$ are joined by an edge. In Section 2, it is proved that the upper bound of chromatic number $chi(${sf KG}$^2(2k+1,k))$ of the square of the Kneser graph {sf KG}$(2k+1,k)$ is reduced from $4k+2$ to $3k+2$ when $kgeq 3$. The emph{reduced Kneser graph} ${sfKG}_2(n,k)$ is the subgraph of the Kneser graph ${sf KG}(n,k)$ induced by all vertices that are 2-stable subsets. In Section 3, it is proved that $chi({sf KG}^2_2(2k+2,k))= 2k+2$ when $k geq 3$ and $chi({sf KG}^2_2(6,2))=9$. In the last section, we define the generalized Coxeter graphs {sf CG}$(p)$ and prove that $frac{p+1}{2} leq chi({sf CG}^2(p)) leq frac{p+3}{2}$ where $p$ is an odd prime.