This thesis constructs special graphs with given circular
chromatic numbers or circular flow numbers.
Suppose $G=(V,E)$ is a graph and $rgeq 2$ is a real number. An
$r$-coloring of a graph $G$ is a mapping $f:V
ightarrow [0,r)$
such that for any adjacent vertices $x,y$ of $G$, $1leq
|f(x)-f(y)|leq r-1$. The circular chromatic number $chi_c(G)$
is the least $r$ for which there exists an $r$-coloring of $G$.
The circular chromatic number was introduced by Vince in 1988 in
cite{vince}, where the parameter is called the {em star
chromatic number} and denoted by $chi^*(G)$. Vince proved that
for any rational number $k/dgeq 2$ there is a graph $G$ with
$chi_c(G)=k/d$. In this thesis, we are interested in the
existence of special graphs with given circular chromatic numbers.
A graph $H$ is called a minor of a graph $G$ if $H$ can be
obtained from $G$ by deleting some vertices and edges, and
contracting some edges. A graph $G$ is called $H$-minor free if
$H$ is not a minor of G. The well-known Hadwiger's conjecture
asserts that for any positive integer $n$, any $K_n$-minor free
graph $G$ is $(n-1)$-colorable. If this conjecture is true, then
for any $K_n$-minor free graph $G$, we have $chi_c(G)leq n-1$.
On the other hand, for any graph $G$ with at least one edge we
have $chi_c(G)geq 2$. A natural question is this: Is it true
that for any rational number $2leq rleq n-1$, there exist a
$K_n$-minor free graph $G$ with $chi_c(G)=r$?
For $n=4$, the answer is ``no". It was proved by Hell and Zhu in
cite{hz98} that if $G$ is a $K_4$-minor free graph then either
$chi_c(G)=3$ or $chi_c(G)leq 8/3$. So none of the rational
numbers in the interval $(8/3,3)$ is the circular chromatic number
of a $K_4$-minor free graph. For $ngeq 5$, Zhu cite{survey}
proved that for any rational number $rin[2,n-2]$, there exists a
$K_n$-minor free graph $G$ with $chi_c(G)=r$. The question
whether there exists a $K_n$-minor free graph $G$ with
$chi_c(G)=r$ for each rational number $rin(n-2,n-1)$ remained
open. In this thesis, we answer this question in the affirmative.
For each integer $ngeq 5$, for each rational number
$rin[n-2,n-1]$, we construct a $K_n$-minor free graph $G$ with
$chi_c(G)=r$. This implies that for each $ngeq 5$, for each
rational number $rin[2,n-1]$, there exists a $K_n$-minor free
graph $G$ with $chi_c(G)=r$. In case $n=5$, the $K_5$-minor free
graphs constructed in this thesis are actually planar graphs. So
our result implies that for each rational number $rin[2,4]$,
there exists a planar graph $G$ with $chi_c(G)=r$. This result
was first proved by Moser cite{moser} and Zhu cite{3-4}. To be
precise, Moser cite{moser} proved that for each rational number
$rin[2,3]$, there exist a planar graph $G$ with $chi_c(G)=r$,
and Zhu cite{3-4} proved that for each rational number
$rin[3,4]$, there exists a planar graph $G$ with $chi_c(G)=r$.
Moser's and Zhu's proofs are quite complicated. Our construction
is conceptually simpler. Moreover, for $ngeq 5$, $K_n$-minor
free graphs, including the planar graphs are constructed with a
unified method.
For $K_4$-minor free graphs, although Hell and Zhu cite{hz98}
proved that there is no $K_4$-minor free graph $G$ with
$chi_c(G)in (8/3,3)$. The question whether there exists a
$K_4$-minor free graph $G$ with $chi_c(G)=r$ for each rational
number $rin[2,8/3]$ remained open. This thesis solves this
problem: For each rational number $rin[2,8/3]$, we shall
construct a $K_4$-minor free $G$ with $chi_c(G)=r$.
This thesis also studies the relation between the circular
chromatic number and the girth of $K_4$-minor free graphs. For
each integer $n$, the supremum of the circular chromatic number of
$K_4$-minor free graphs of odd girth (the length of shortest odd
cycle) at least $n$ is determined. It is also proved that the
same bound is sharp for $K_4$-minor free graphs of girth $n$.
By a classical result of ErdH{o}s, for any positive integers $l$
and $n$, there exists a graph $G$ of girth at least $l$ and of
chromatic number $n$. Using probabilistic method, Zhu
cite{unique} proved that for each integer $l$ and each rational
number $rgeq 2$, there is a graph $G$ of girth at least $l$ such
that $chi_c(G)=r$. Construction of such graphs for $rgeq 3$ was
given by Nev{s}etv{r}il and Zhu cite{nz}. The question of how
to construct large girth graph $G$ with $chi_c(G)=r$ for given
$rin(2,3)$ remained open. In this thesis, we present a unified
method that constructs, for any $rgeq 2$, a graph $G$ of girth
at least $l$ with circular chromatic number $chi_c(G) =r$.
Graphs $G$ with $chi_c(G)=chi(G)$ have been studied extensively
in the literature. Many families of graphs $G$ are known to
satisfy $chi_c(G)=chi(G)$. However it remained as an open
question as how to construct arbitrarily large $chi$-critical
graphs $G$ of bounded maximum degree with $chi_c(G)=chi(G)$.
This thesis presents a construction of such graphs.
The circular flow number $Phi_c(G)$ is the dual concept of
$chi_c(G)$. Let $G$ be a graph. Replace each edge $e=xy$ by a
pair of opposite arcs $a=overrightarrow{xy}$ and
$a^{-1}=overrightarrow{yx}$. We obtain a symmetric directed
graph. Denote by $A(G)$ the set of all arcs of $G$. A chain is a
mapping $f:A(G)
ightarrow I!!R$ such that for each arc $a$,
$f(a^{-1})=-f(a)$. A flow is a chain such that for each subset
$X$ of $V(G)$, $sum_{ain[X,ar{X}]}f(a)=0$, where
$[X,ar{X}]$ is the set of all arcs from $X$ to $V-X$. An
$r$-flow is a flow such that for any arc $ain A(G)$ , $1leq
|f(a)| leq r-1$. The circular flow number of $G$ is
$Phi_c(G)=mbox{ inf}{r: G mbox{ admits a } rmbox{-flow}}$.
It was conjectured by Tutte that every graph $G$ has
$Phi_c(G)leq 5$. By taking the geometrical dual of planar
graphs, Moser's and Zhu's results concerning circular chromatic
numbers of planar graphs imply that for each rational number
$rin[2,4]$, there is a graph $G$ with $Phi_c(G)=r$. The question
remained open whether for each $rin(4,5)$, there exists a graph
$G$ with $Phi_c(G)=r$. In this thesis, for each rational number
$rin [4,5]$, we construct a graph $G$ with $Phi_c(G)=r$.
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0627103-111233 |
| Date | 27 June 2003 |
| Creators | Pan, Zhi-Shi |
| Contributors | Chin-Mei Fu, D. J. Guan, Xuding Zhu, Hung-Lin Fu, Hong-Gwa Yeh, Li-Da Tong |
| Publisher | NSYSU |
| Source Sets | NSYSU Electronic Thesis and Dissertation Archive |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0627103-111233 |
| Rights | unrestricted, Copyright information available at source archive |
Page generated in 0.0028 seconds