臺灣博碩士論文加值系統

一個圖函數是一個映射 f，它賦予每個圖 H 一個正整數
f(H)，使得 f(H) 不大於H 的頂點數且同構的圖皆有相同的賦值。給定一個圖 G 和一個圖函數 f，映射 c 被稱為 G 的一個 f-著色，如果對於G 的任意子圖 H，|c(H)|≦ f(H)。圖 G 的 f-色數是圖 G 的一個 f-著色所需要的最少顏色數。圖 G 的 f-色數是色數的一個自然推廣。它是 Nešetřil 與 Ossena de Mendez 首先定義的。直觀地來看，圖G 的f-色數就是在對於某些特定子圖必須給予足夠多顏色限制條件下，用最少的顏色來著色圖 G 的全部頂點。原始的著色以及諸多其他著色的推廣都是 f-著色的特例。例如，圖的色數就是用最少的顏色來著色圖的頂點，但要求每一 K_2 -子圖用到 2 種顏色。圖的無圈色數也是用最少的顏色來著色圖的頂點，但要求每一K_2-子圖用到 2 種顏色，且每一個圈至少用到 3 種顏色。

本論文探討對局型形式的 f-著色。定義如下：假設 G 是一個圖且 X 是顏色集。甲和乙兩人輪流在圖 G 的頂點上用 X 中的顏色著色。一個圖 G 的部份著色被稱之為合法的 (對於圖函數 f 而言) ，如果對於任意圖 G 的子圖 H 而言，H 上所用的顏色數加上 H 未被著色的頂點數之和不小於f(H)。甲和乙都必須用合法的方式著色(合法的定義是被作出部份著色是合法的)。如果所有的頂點都被著色或是某些頂點沒有合法的顏色可以著色時，這個遊戲就會結束。如果這個遊戲時，所有的頂點都被著色，則甲獲勝；否則，則為乙獲勝。圖 G 的 f-對局色數就是甲有必勝策略之最小顏色集 X 的元素個數。很明顯的，如果 X 的集合大小等於頂點數，甲必然獲勝。所以 f-對局色數是定義明確的。我們定義圖 G 的f-對局邊色數就是對於 G 之線圖的 f-對局色數。

一個關於對局色數很自然的問題就是：什麼樣的圖函數
f，使得對於某些自然圖族上的所有圖 G，G 的 f-對局色數為有界？如果在有界的情形下，其最小上界為何？本文探討對於某些特殊圖函數及某些特殊圖族的對局色數或是對局邊色數。文中討論下列三類圖函數：
1. d-鬆弛函數，記做 Rel_d，定義為：Rel_d(K_{1,d+1})=2；除此以外的圖 H ，Rel_d(H)=1。
2. 無圈函數，記做 Acy，定義為：Acy(K_2)=2；對於所有長度 n ≦ 3 的圈 C_n 而言， Acy(C_n)=3；除此以外的圖 H，Acy(H)=1。
3. i-路徑函數，記做 Path_i，定義為：Path_i(K_2)=2；
對於 i 個頂點的路徑 P_i 而言，Path_i(P_i)=3；除此以外的圖 H，Path_i(H)=1。

討論的圖族主要是外平面圖，森林，k-退化圖的線圖這三類。在第二章，我們討論外平面圖的無圈對局色數。我們證明，對於所有外平面圖 G，G 的 Acy-對局色數小於等於7。另一方面，我們證明，可以找到一外平面圖 G$ 使得 G 的 Acy-對局色數大於等於 6。更進一步，對於任意給定的正整數 n，我們可以找到一個串並聯圖 G_n 使得 G_n 的 Acy-對局色數大於n。

第三章中，我們討論在森林上的 Path_i-對局色數。已經得到的是，當 i ≧ 8，對於任意的森林 F，F 的 Path_i-對局色數小於等於 9。另一方面，當 i ≦6，對於一個任意的整數 k，我們可以找到一個樹 T，使得 T 的 Path_i-對局色數大於等於 n。

第四章中，我們研究在 k-退化圖的 d-鬆弛對局邊色數。
已經得到的是，當 d ≦ 2k^2 + 5k-1 且 G 是 k-退化圖，我們有G的d-鬆弛對局邊色數小於等於2k + (Δ(G)+k-1)(k+1)}/(d-2k^2-4k+2)。另一方面, 對於任意正整數 d ≦ Δ -2，我們可以找到一個最大度為 Δ 的樹 T，使得 G 的 d-鬆弛對局邊色數大於等於 2Δ / (d+3)。更進一步，我們證明，當 d ≧ 2k + 2 [ ( Δ (G) - k ) / 2 ] +1 且 G 是 k-退化圖，有 G 的 d-鬆弛對局邊色數小於等於2 。

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.

1 Introduction 1
1.1 Game chromatic number of graphs 1
1.2 Marking game 3
1.3 Graph functions and generalizations of chromatic number 6
1.4 Tree-depth of graphs 10
1.5 f-Game Chromatic number 10
1.6 Overview of known results 11
1.7 Results of this thesis 12

2 Acyclic game chromatic number 15
2.1 Definition and example 15
2.2 Outerplanar graphs 16
2.3 Series parallel graphs 19

3 Path_k-game chromatic number 20
3.1 Definitions and examples 20
3.2 Pathk-game chromatic number of forests for k ≧8 21
3.3 Pathk-game chromatic number of forests for k ≦ 6 31

4 Rel_d-game chromatic index 35
4.1 Known results 35
4.2 An upper bound for the Rel_d-game chromatic index of k-degenerated graphs 36
4.3 The lower bound of the Rel_d-game chromatic index on trees 40
4.4 Colouring k-degenerated graphs with 2 colours 42

5 Conclusions and further questions 44
5.1 Conclusions 44
5.2 Further questions 45

[1] T. Bartnicki, J. Grytczuk, and H. A. Kierstead. The game of arboricity. DMTCS
Conference Volume AE, pages 63–66, 2005.
[2] H. L. Bodlaender. On the complexity of some coloring games. In Graph-theoretic
concepts in computer science (Berlin, 1990), volume 484 of Lecture Notes in Comput.
Sci., pages 30–40. Springer, Berlin, 1991.
[3] O. V. Borodin. On acyclic colorings of planar graphs. Discrete Math., 25(3):211–236,
1979.
[4] L. Cai and X. Zhu. Game chromatic index of k-degenerate graphs. J. Graph Theory,
36(3):144–155, 2001.
[5] H. Chang and X. Zhu. The d-relaxed game chromatic index of k-degenerated graphs.
Australas. J. Combin., 36:73–82, 2006.
[6] C. Chou, W.Wang, and X. Zhu. Relaxed game chromatic number of graphs. Discrete
Math., 262(1-3):89–98, 2003.
[7] T. Dinski and X. Zhu. A bound for the game chromatic number of graphs. Discrete
Math., 196(1-3):109–115, 1999.
[8] C. Dunn. The relaxed game chromatic index of k-degenerate graphs. Dsicrete Mathematics,
to appear.
[9] C. Dunn and H. A. Kierstead. The relaxed game chromatic number of outerplanar
graphs. J. Graph Theory, 46(1):69–78, 2004.
[10] C. Dunn and H. A. Kierstead. A simple competitive graph coloring algorithm. II. J.
Combin. Theory Ser. B, 90(1):93–106, 2004. Dedicated to Adrian Bondy and U. S.
R. Murty.
[11] U. Faigle, U. Kern, H. A. Kierstead, and W. T. Trotter. On the game chromatic
number of some classes of graphs. Ars Combin., 35:143–150, 1993.
[12] M. Gardner. Martin Gardner’s mathematical games. MAA Spectrum. Mathematical
Association of America, Washington, DC, 2005. The entire collection of his Scientific
American columns, With a booklet containing a biography of the author by Donald
J. Albers and Peter L. Renz.
[13] D. Guan and X. Zhu. Game chromatic number of outerplanar graphs. J. Graph
Theory, 30(1):67–70, 1999.
[14] W. He, J. Wu, and X. Zhu. Relaxed game chromatic number of trees and outerplanar
graphs. Discrete Math., 281(1-3):209–219, 2004.
[15] H. A. Kierstead. A simple competitive graph coloring algorithm. J. Combin. Theory
Ser. B, 78(1):57–68, 2000.
[16] H. A. Kierstead. Asymmetric graph coloring games. J. Graph Theory, 48(3):169–185,
2005.
[17] H. A. Kierstead. Weak acyclic coloring and asymmetric coloring games. Discrete
Math., 306(7):673–677, 2006.
[18] H. A. Kierstead and W. T. Trotter. Planar graph coloring with an uncooperative
partner. J. Graph Theory, 18(6):569–584, 1994.
[19] H. A. Kierstead and W. T. Trotter. Competitive colorings of oriented graphs. Electron.
J. Combin., 8(2):Research Paper 12, 15 pp. (electronic), 2001. In honor of
Aviezri Fraenkel on the occasion of his 70th birthday.
[20] H. A. Kierstead and Z. Tuza. Marking games and the oriented game chromatic
number of partial k-trees. Graphs Combin., 19(1):121–129, 2003.
[21] H. A. Kierstead and D. Yang. Very asymmetric marking games. Order, 22(2):93–107
(2006), 2005.
[22] J. Neˇsetˇril and P. Ossona de Mendez. Tree-depth, subgraph coloring and homomorphism
bounds. European J. Combin., 27(6):1022–1041, 2006.
[23] J. Neˇsetˇril and E. Sopena. On the oriented game chromatic number. Electron. J.
Combin., 8(2):Research Paper 14, 13 pp. (electronic), 2001. In honor of Aviezri
Fraenkel on the occasion of his 70th birthday.
[24] B. Shen. Trees with more simple structure and the relaxed game chromatic number
3. J. Baoji Univ. Arts Sci. Math. Colloq. Chin. Univ., (3B):181–183, 2006.
[25] J. Wu and X. Zhu. Relaxed game chromatic number of outer planar graphs. Ars
Combin., 81:359–367, 2006.
[26] J. Wu and X. Zhu. The 6-relaxed game chromatic number of outerplanar graphs.
Dsicrete Mathematics, to appear.
[27] X. Zhu. The game coloring number of planar graphs. J. Combin. Theory Ser. B,
75(2):245–258, 1999.
[28] X. Zhu. The game coloring number of pseudo partial k-trees. Discrete Math., 215(1-
3):245–262, 2000.
[29] X. Zhu. Refined activation strategy for the marking game. J. Combin. Th. Ser. B,
(2007), doi: 10.1016/j.jctb.2007.04.004.