This thesis studies the circular chromatic number of Kneser graphs. It was known that if m is greater than 2n^{2}(n-1), then the Kneser graph KG(m,n) has its circular chromatic number equal its chromatic number . In particular, if n = 3, then KG(m,3) has its circular chromatic number equal its chromatic number when m is greater than 36. In this thesis, we improve this result by proving that if m is greaer than 24, then chi_c(KG(m,3)) = chi(KG(m,3)).

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$.

In (J Graph Theory 33 (2000), 14-24), Hell and Zhu proved that if a series-parallel graph G has girth at least 2⌊(3k-1)/2⌋, then χc(G)≤4k/(2k-1). In (J Graph Theory 33 (2000), 185-198), Chien and Zhu proved that the girth condition given in (J Graph Theory 33 (2000), 14-24) is sharp. Short proofs of both results are given in this note.

This thesis discusses colouring, circular list colouring and adapted game colouring of graphs. For colouring, this thesis obtains a sufficient condition for a planar graph to be 3-colourable. Suppose G is a planar graph. Let H_G be the graph with vertex set V (H_G) = {C : C is a cycle of G with |C| ∈ {4, 6, 7}} and edge set E(H_G) = {CiCj : Ci and Cj have edges in common}. We prove that if any 3-cycles and 5-cycles are not adjacent to i-cycles for 3 ≤ i ≤ 7, and H_G is a forest, then G is 3-colourable. For circular consecutive choosability, this thesis obtains a basic relation among chcc(G), X(G) and Xc(G) for any finite graph G. We show that for any finite graph G, X(G) − 1 ≤ chcc(G) < 2 Xc(G). We also determine the value of chcc(G) for complete graphs, trees, cycles, balanced complete bipartite graphs and some complete multi-partite graphs. Upper and lower bounds for chcc(G) are given for some other classes of graphs. For adapted game chromatic number, this thesis studies the adapted game chromatic number of various classes of graphs. We prove that the maximum adapted game chromatic number of trees is 3; the maximum adapted game chromatic number of outerplanar graphs is 5; the maximum adapted game chromatic number of partial k-trees is between k + 2 and 2k + 1; and the maximum adapted game chromatic number of planar graphs is between 6 and 11. We also give upper bounds for the Cartesian product of special classes of graphs, such as the Cartesian product of partial k-trees and outerplanar graphs, or planar graphs.