Details

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

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 Location:China - Taiwan

Source Type:Master's Thesis

Keywords:circular chromatic number flow

ISBN:

Date of Publication:06/27/2003