• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Game Colourings of Graphs

Chang, Hung-yung 09 August 2007 (has links)
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.

Page generated in 0.0782 seconds