\documentclass{ctwart}
\pagestyle{plain}
%\textheight 30cm
%\textwidth 18cm
%\topmargin -2cm
%\oddsidemargin -1.0cm
%\evensidemargin -5.0cm
\usepackage{amssymb}
%\usepackage{endmmacro}
\usepackage{graphicx}
\newtheorem{theorem}{Théorème}[section]
\newtheorem{lemma}[theorem]{Lemme}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollaire}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{definition}[theorem]{Définition}
\newenvironment{proof}{
\noindent {\bf Preuve:}\rm}%
{\mbox{}\hfill\rule{0.5em}{0.809em}\par\vskip 5mm}
\newenvironment{remark}[1][Remarque:]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{exemple}[1][Exemple:]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\usepackage{color}
\usepackage{epsfig}
\newcommand{\red}[1]{\textcolor{red}{#1}}
\newcommand{\blu}[1]{\textcolor{blue}{#1}}
\newcommand{\gre}[1]{\textcolor{green}{#1}}
%\newcommand{\A}[0]{\cal A}}
\def\gcn{game chromatic number }
\def\A{\mathcal{A}}
\def\B{\mathcal{B}}
\def\C{\mathcal{C}}
\def\F{\mathcal{F}}
\def\N{\mathcal{N}}
\def\P{\mathcal{P}}
\def\T{\mathcal{T}}
\def\X{\mathcal{X}}
\def\Y{\mathcal{Y}}
\begin{document}
\setcounter{page}{73}
\begin{frontmatter}
\title{The game chromatic number of 1-caterpillars}
\author{Adrien Guignard\thanksref{myemail}}
\address{
Universit\'e de Bordeaux\\
LaBRI UMR 5800\\
351, cours de la Lib\'eration \\
F-33405 Talence Cedex, France}
\thanks[myemail]{Email:{\texttt{guignard@labri.fr}}}
\begin{abstract}
The game chromatic number of a graph is defined using a two players game. In 1993, Faigle et al. proved that the game chromatic number of trees is at most four.
In this paper we investigate the problem of characterizing those trees with game chromatic number three, and setttle this problem for 1-caterpillars.
\end{abstract}
\begin{keyword}
game chromatic number, caterpillar, tree, leaf.
\end{keyword}
\end{frontmatter}
\section{Introduction}
The game chromatic number of a graph $G$, denoted by $\chi_{g}(G)$, is defined through a \textit{coloring game} with two players Alice and Bob and a set of $k$ colors. Each move by either player consists of coloring an uncolored node of $G$ with a color $i$ of the set. Adjacent vertices must be colored by distinct colors. The game ends if no more vertices can be colored. Alice wins the game if all vertices are colored. Otherwise, Bob wins.\\
The game chromatic number $\chi_{g}(G)$ is the least number of colors for which Alice has a winning strategy in this game.
This parameter was introduced by Bodlaender \cite{Bod} (see also \cite{Sur} for a recent survey). Since then the problem has attracted considerable attention and has been studied for various classes of graphs \cite{Kie} \cite{Gua}. For instance, it is proved by Zhu \cite{Zhu} that if $P$ is a planar graph then $\chi_g(P)\leq 17$.
Faigle et al. \cite{Fai} proved that the \gcn of every tree is at most four. A natural question in this framework is to characterize the trees with given \gcn $k$, for $1\leq k\leq 4$. Since the answer is obvious for $k=1,2$, our aim is to characterize the set of trees with \gcn three.
The general characterization seems to be a difficult problem. Therefore, we restrict ourselves to the set of caterpillars and settle the problem for 1-caterpillars.
%In 1999, Shu-Yu Tsai [???] has studied this problem and proved that if a 1-caterpillar has at least diameter $102$, then its \gcn is $4$. In this paper we improve this result end determine exactly for which 1-caterpillars the \gcn is $4$.
\section{Definitions and properties}
A tree is called a \textit{caterpillar} if a path remains after the removal of all its leaves. This path is called the \textit{spine} of the caterpillar. A \textit{1-caterpillar} is a caterpillar such that every vertex of the spine is a neighbor of exactly one leaf, except for the two extremities of the spine that have two leaves.
Since the game chromatic number of a caterpillar $C$ is at most 4, we will play with three colors and determine whether Alice can complete the coloration of $C$ or not. If it is possible, we will say that Alice wins and otherwise that Bob wins.
We denote by $[C,c]$ a caterpillar $C$ equipped with a partial coloring $c$ of its vertices. Such a caterpillar will be simply denoted by $C$ whenever the partial coloring $c$ is clear from the context.
To compute the game chromatic number of caterpillars, we have to know for any $[C,c]$ not only whoever wins if Alice begins, but also if Bob begins.
We thus define the \textit{outcome} of a partially colored caterpillar $C$, denoted by $o(C)$, as follows:
\begin{enumerate}
\item $o(C)=\B$ if \textbf{Bob} wins whoever starts the game;
\item $o(C)=\P$ if the next player loses (so the \textbf{Previous} one wins);
\item $o(C)=\N$ if the \textbf{Next} player wins;
\item $o(C)=\A$ if \textbf{Alice} wins whoever starts the game.
\end{enumerate}
We denote by $Opt(C)$ the set of options of $C$, that is the set of partially colored caterpillars that can be obtained from $C$ after one move. If $C$ has an option with outcome $\X$, we say that $C$ has an \textit{$\X$-option}.
We extend the definition of outcome to a set of caterpillars $\C$: $o(\C)=\big\{ o(C),\ C\in\C\big\}$.
\begin{proposition}
\label{outcomeOpt}
Let $C$ be a not totally colored caterpillar.
\begin{enumerate}
\item $ o(C)=\B \Leftrightarrow o(Opt(C))\in \bigg\{ \{\B\}\ ,\ \{\N,\B\}\bigg\}$;
\item $ o(C)=\P \Leftrightarrow o(Opt(C))=\{\N\}$;
\item $ o(C)=\N \Leftrightarrow \ o(Opt(C))$ contains $\P$, or contains $\A$ and $\B$;
\item $ o(C)=\A \Leftrightarrow o(Opt(C))\in \bigg\{ \{\A\}\ ,\ \{\A,\N\}\bigg\}$.
\end{enumerate}
\end{proposition}
Since we will need to consider outcomes of disjoint unions of caterpillars, we need some properties to compute $o(C_1\cup C_2)$ according to $o(C_1)$ and $o(C_2)$ (where $C_1\cup C_2$ denotes the disjoint union of $C_1$ and $C_2$).\\
We call the \textit{signed outcome} of $C$ the outcome $\X$ of $C$ signed by the parity of the number of uncolored nodes of $C$, denoted by $o'(C)=\X_0$ or $\X_1$.
\begin{proposition}
\label{AddOutcomes}
Firstly, if $o(C_1)=\B$ or $o(C_2)=\B$ then $o(C_1\cup C_2)=\B$. Otherwise, we define an addition function of signed outcomes, denoted by "$\oplus$", that satisfies $o'(C_1\cup C_2)=o'(C_1)\oplus o'(C_2)$, and is given by the following table:
\begin{center}
\begin{tabular}{c||c|c|c|c|c|c|}
$\oplus$ & \red{$\P_0$} & \red{$\P_1$} & \blu{$\N_0$} & \blu{$\N_1$} & \gre{$\A_0$} & \gre{$\A_1$} \\\hline\hline
\red{$\P_0$} & \red{$\P_0$} & $\B_1$ & $\B_0$ & \blu{$\N_1$} & \red{$\P_0$} & \blu{$\N_1$} \\\hline
\red{$\P_1$} & $\B_1$ & $\B_0$ & $\B_1$ & \blu{$\N_0$} & \red{$\P_1$} & \blu{$\N_0$} \\\hline
\blu{$\N_0$} & $\B_0$ & $\B_1$ & $\B_0$ & $\B_1$ & \blu{$\N_0$} & \blu{$\N_1$} \\\hline
\blu{$\N_1$} & \blu{$\N_1$} & \blu{$\N_0$} & $\B_1$ & $\B_0$ & \blu{$\N_1$} & \blu{$\N_0$} \\\hline
\gre{$\A_0$} & \red{$\P_0$} & \red{$\P_1$} & \blu{$\N_0$} & \blu{$\N_1$} & \gre{$\A_0$} & \gre{$\A_1$} \\\hline
\gre{$\A_1$} & \blu{$\N_1$} & \blu{$\N_0$} & \blu{$\N_1$} & \blu{$\N_0$} & \gre{$\A_1$} & \gre{$\A_0$} \\\hline
\end{tabular}
\end{center}
\end{proposition}
We note $\preceq$ the relation on the set of outcomes $\{\B,\P,\N,\A\}$ such that:
\begin{enumerate}
\item $\A\preceq\N\preceq\B$
\item $\P$ and every another outcome $\X$ are incomparables.
\end{enumerate}
If $T$ and $U$ are two partially colored caterpillars, we say that $T$ is a subgraph of $U$ and note $T\subseteq U$ if and only if $V(T)\subseteq V(U)$, $E(T)\subseteq E(U)$ and $\forall v\in V(T)$, $c_T(v)=c_U(v)$ (where $c_T(v)$ is the color of $v$ in $T$).
\begin{proposition}
\label{sub}
Let $T$ and $U$ be two partially colored caterpillars. If $T\subseteq U$ then $o(T)\preceq o(U)$
\end{proposition}
Let $C$ be a partially colored caterpillar. Observe that if $C$ has an uncolored vertex $v$ having three neighbours colored with distinct colors, then the outcome is $\B$ (since $v$ cannot be colored). Similary, if $C$ has a colored node $v$ with degree $k\geq 2$, the forest $C'$ obtained from $C$ by splitting $v$ into $k$ colored leaves with the same color than $v$, each linked to a neighbour of $v$ (thus creating $k$ connected components) is equivalent to $C$ (we mean $o'(C')=o'(C)$).
Finally, if $C$ has an uncolored node $v$ with two leaves colored with the same color, the caterpillar $C'$ obtained from $C$ by deleting one of these two leaves is equivalent to $C$.
\section{The family of 1-caterpillars}
Let $C$ be a partially colored 1-caterpillar whose spine $s_1s_2\dots s_{\ell}$ contains no colored vertices. Moreover let $s_0$ (resp. $s_{\ell+1}$) be one of the two leaves connected to $s_1$ (resp. $s_{\ell}$).
The leaves connected to $s_1$ or $s_{\ell}$ are the \textit{ends} of $C$.
We associate with $C$ a word $w(C)=w_0\dots w_{\ell+1}$ on the alphabet $\{z,1,2,3\}$ defined as follows: $w_0$ is the color of $s_0$ if it is colored or $z$ otherwise (the same is true of $w_{\ell+1}$), and for every $i$, $1\leq i\leq \ell$, $w_i$ is the color of the leaf connected to $s_i$, or $z$ if this leaf is not colored.
For instance, the following caterpillar is associated with the word $1zz2z2$.
\begin{center}
\includegraphics[scale=0.4]{Caterpillar.eps}
\end{center}
Using properties of outcomes and subgraphs, we prove the following results.
\begin{theorem}
Let $C$ be a 1-catepillar with $w(C)=az^nb$ and $a,b\in \{1,2,3\}$. The outcome of $C$ is given by the following table:\\
\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|}\hline
n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\\hline
$o(C)$ & $\A\N$ & $\A$ & $\N$ & $\A$ & $\N$ & $\A$ & $\N$ & $\A\N$ & $\N$ \\\hline \hline
n & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & $\geq 18$ \\\hline
$o(C)$ & $\N$ & $\N$ & $\N$ & $\N$ & $\N\B$ & $\N$ & $\B$ & $\N\B$ & $\B$\\\hline
\end{tabular}
where $\X\Y$ stands for $\X$ if $a=b$ and $\Y$ otherwise.
\end{theorem}
The proof relies on several lemmas which consider the outcomes of some 1-caterpillars with particular partial colorings.
We proceed by studying a family $\F$ of caterpillars (for instance $a z^{2n} b b$ with $n\geq 0$) and compute the value $n$ defined as the smallest size of a caterpillar with outcome $\N$ (resp. $\B$), so that every smaller caterpillar in $\F$ has outcome $\A$ (resp. $\A$ or $\N$). We also have to check that no 1-caterpillar of this family has outcome $\P$.
\begin{theorem}
Let $C$ an uncolored 1-caterpillar with $n$ nodes of degree $3$.
\begin{enumerate}
\item If $n\geq 28$ then $o(C)=\B$
\item If $23\leq n\leq 27$ then $o(C)=\N$
\item Otherwise $o(C)=\A$
\end{enumerate}
\end{theorem}
\begin{thebibliography}{00}
%\begin{thebibliography}{10}\label{bibliography}
\bibitem{Bod} H. L. Boadlaender, \emph{On the complexity of some coloring games}, Int. J. Found Comput. Sci. \textbf{2}(2) (1991), 133--147.
\bibitem{Fai} U. Faigle, U. Kern, H. A. Kierstead and W. T. Trotter, \emph{On the game chromatic number of some classes of graphs}, Ars Combin \textbf{35} (1993), 143--150.
\bibitem{Sur} T. Bartnicky, J. Grytczuk, H. A. Kierstead and X. Zhu, \emph{The map coloring game}, Am. Math. Monthly, \textbf{114} (2007), 793--803.
\bibitem{Kie} H. A. Kierstead and W. T. Trotter, \emph{Planar graph coloring with an uncooperative partner}, J. Graph Theory \textbf{18}(6) (1994), 569-584.
\bibitem{Gua} D. Guan and X. Zhu, \emph{The game chromatic number of outerplanar graphs}, J. Graph Theory \textbf{30}(1999), 67--70.
\bibitem{Zhu} X. Zhu, \emph{Refined activation strategy for the marking game}, J. Combin. Theory Ser. B \textbf{98}(1) (2008), 1--18
\end{thebibliography}
\end{document}