A graph function $f$ is a mapping which assigns each graph $H$
a positive integer $f(H)
leq |V(H)|$ such that $f(H)=f(H')$ if $H$ and $H'$ are
isomorphic. Given a graph function $f$ and a graph $G$, an
$f$-colouring of $G$ is a mapping $c: V(G) o
mathbb{N}$ such that every subgraph $H$ of $G$ receives at least
$f(H)$ colours, i.e., $|c(H)| geq f(H)$. The $f$-chromatic
number, $chi(f,G)$, is the minimum number of colours used in an
$f$-colouring of $G$. The $f$-chromatic number of a graph is a
natural generalization of the chromatic number of a graph
introduced by Nev{s}etv{r}il and Ossena de Mendez. Intuitively,
we would like to colour the vertices of a graph $G$ with minimum
number of colours subject to the constraint that the number of
colours assigned to certain subgraphs must be large enough. The
original chromatic number of a graph and many of its
generalizations are of this nature. For example, the chromatic
number of a graph is the least number of colours needed to colour
the vertices of the graph so that any subgraph isomorphic to
$K_2$ receives $2$ colours. Acyclic chromatic number of a graph is
the least number of colours needed to colour the vertices of the
graph so that any subgraph isomorphic to $K_2$ receives $2$
colours, and each cycle receives at least $3$ colours.
This thesis studies the game version of $f$-colouring of graphs.
Suppose $G$ is a graph and $X$ is a set of colours. Two players,
Alice and Bob, take turns colour the vertices of $G$ with colours
from the set $X$. A partial colouring of $G$ is legal (with respect
to graph function $f$) if for any subgraph $H$ of $G$, the sum of
the number of colours used in $H$ and the number of uncoloured
vertices of $H$ is at least $f(H)$. Both Alice and Bob must colour
legally (i.e., the partial colouring produced needs to be legal).
The game ends if either all the vertices are coloured or there are
uncoloured vertices but there is no legal colour for any of the
uncoloured vertices. In the former case, Alice wins the game. In the
latter case, Bob wins the game. The $f$-game chromatic number of
$G$, $chi_g(f, G)$, is the least number of colours that the colour
set $X$ needs to contain so that Alice has a winning strategy.
Observe that if $|X| = |V(G)|$, then Alice always wins. So the
parameter $chi_g(f,G)$ is well-defined. We define the $f$-game
chromatic index on a graph $G$, $chi'(f,G)$, to be the $f$-game
chromatic number on the line graph of $G$.
A natural problem concerning the $f$-game chromatic number of graphs
is for which graph functions $f$, the $f$-game chromatic number of
$G$ is bounded by a constant for graphs $G$ from some natural
classes of graphs. In case the $f$-game chromatic number of a class
${cal K}$ of graphs is bounded by a constant, one would like to
find the smallest such constant. This thesis studies the $f$-game
chromatic number or index for some special classes of graphs and for
some special graph functions $f$. The graph functions $f$ considered
are the following graph functions:
1. The $d$-relaxed function, ${
m Rel}_d$, is defined as ${
m Rel}_d(K_{1,d+1})=2$ and ${
m Rel}_d(H)=1$ otherwise.
2. The acyclic function, ${
m Acy}$, is defined as ${
m Acy}(K_2)=2$ and ${
m Acy}(C_n)=3$ for any $n geq 3$ and
${
m Acy}(H)=1$ otherwise.
3. The $i$-path function, ${
m Path}_i$, is defined as ${
m Path}_i(K_2)=2$ and
${
m Path}_i(P_i)=3$ and ${
m Path}_i(H)=1$ otherwise, where $P_i$
is the path on $i$ vertices.
The classes of graphs considered in the thesis are outerplanar
graphs, forests and the line graphs of $d$-degenerate graphs. In
Chapter 2, we discuss the acyclic game chromatic number of
outerplanar graphs. It is proved that for any outerplanar graph $G$,
$chi_g({
m Acy},G) leq 7$. On the other hand, there is an
outerplanar graph $G$ for which $chi_g({
m Acy},G) = 6$. So the
best upper bound for $chi_g({
m Acy},G)$ for outerplanar graphs is
either $6$ or $7$. Moreover, we show that for any integer $n$, there
is a series-parallel graph $G_n$ with $chi_g({
m Acy}, G_n)
> n$.
In Chapter 3, we discuss the ${
m Path}_i$-game chromatic number
for forests. It is proved that if $i geq 8$, then for any forest
$F$, $chi_g({
m Path}_i, F) leq 9$. On the other hand, if $i
leq 6$, then for any integer $k$, there is a tree $T$ such that
$chi_g({
m Path}_i, T) geq k$.
Chapter 4 studies the $d$-relaxed game chromatic indexes of
$k$-degenerated graphs. It is proved that if $d geq 2k^2 + 5k-1$
and $G$ is $k$-degenerated, then $chi'_{
m g}({
m Rel}_d,G)
leq 2k + frac{(Delta(G)+k-1)(k+1)}{d-2k^2-4k+2}$. On the other hand,
for any positive integer $ d leq Delta-2$, there is a tree $T$
with maximum degree $Delta$ for which $chi'_g({
m Rel}_d, T)
geq frac{2Delta}{d+3}$. Moreover, we show that $chi'_g({
m Rel}_d, G) leq
2$ if $d geq 2k + 2lfloor frac{Delta(G)-k}{2}
floor +1$ and
$G$ is a $k$-degenerated graph.
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0809107-161710 |
| Date | 09 August 2007 |
| Creators | Chang, Hung-yung |
| Contributors | Wun-Seng Chou, H. G. Yeh, Tsai-Lien Wong, D. J. Guan, Li-Da Tong, TUNG-SHAN FU, Xuding Zhu, GERARD-JENNHWA CHANG |
| 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-0809107-161710 |
| Rights | unrestricted, Copyright information available at source archive |
Page generated in 0.1405 seconds