Details

Construction of Graphs with Given Circular Chrotmatic Number or Circular Flow number

by Pan, Zhi-Shi

Abstract (Summary)
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$.
Bibliographical Information:

Advisor:Chin-Mei Fu; D. J. Guan; Xuding Zhu; Hung-Lin Fu; Hong-Gwa Yeh; Li-Da Tong

School:National Sun Yat-Sen University

School Location:China - Taiwan

Source Type:Master's Thesis

Keywords:circular chromatic number flow

ISBN:

Date of Publication:06/27/2003

© 2009 OpenThesis.org. All Rights Reserved.