Kneser圖的平方著色
The Coloring of Square of Subgraphs of Kneser Graphs
Date Issued
2004
Date
2004
Author(s)
Chen, Jun-Yo
DOI
en-US
Abstract
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.
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.
Subjects
L(2,1)標號, Coxeter圖
Kneser圖
著色數
平方圖
reduced Knesergraph
Kneser graph
Coxeter graph}
$L(2,1)$-labeling
square graph
chromatic number
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-93-R90221014-1.pdf
Size
23.53 KB
Format
Adobe PDF
Checksum
(MD5):430e47a3fcaf898c6a2db8c245fa344e