% Template article for preprint document class `elsart'
% SP 2001/01/05

% Modified 2007/01/09 for CTW 2010
% Please find the original file at http://www.elsevier.com/

\documentclass{ctwart}

% Use the option doublespacing or reviewcopy to obtain double line spacing
% \documentclass[doublespacing]{elsart}


%\newtheorem{obs}{Observation}
%\newtheorem{theorem}[obs]{Theorem}
%\newtheorem{lemma}[obs]{Lemma}
%\newtheorem{claim}[obs]{Claim}
%\newtheorem{problem}[obs]{Problem}

%\setcounter{bottomnumber}{3}
%\setcounter{totalnumber}{3}

%\renewcommand{\bottomfraction}{0.7}
%\renewcommand{\textfraction}{0.3}
%\renewcommand{\floatpagefraction}{0.7}

% if you use PostScript figures in your article
% use the graphics package for simple commands
% \usepackage{graphics}
% or use the graphicx package for more complicated commands
% \usepackage{graphicx}
% or use the epsfig package if you prefer to use the old commands
\usepackage{epsfig}

% The amssymb package provides various useful mathematical symbols
\usepackage{amssymb}

\begin{document}

\setcounter{page}{9}
\begin{frontmatter}

% Title, authors and addresses

% use the thanksref command within \title, \author or \address for footnotes;
% use the corauthref command within \author for corresponding author footnotes;
% use the ead command for the email address,
% and the form \ead[url] for the home page:
% \title{Title\thanksref{label1}}
% \thanks[label1]{}
% \author{Name\corauthref{cor1}\thanksref{label2}}
% \ead{email address}
% \ead[url]{home page}
% \thanks[label2]{}
% \corauth[cor1]{}
% \address{Address\thanksref{label3}}
% \thanks[label3]{}

\title{The classification of $B$-perfect graphs}

% use optional labels to link authors explicitly to addresses:
% \author[label1,label2]{}
% \address[label1]{}
% \address[label2]{}

%\author{yy}
\author{Stephan Dominique Andres}
\ead{dominique.andres@fernuni-hagen.de}
\ead[url]{http://www.fernuni-hagen.de/MATHEMATIK/DMO/mitarbeiter/andres.html}
\address{Department of Mathematics and Computer 
Science, FernUniversit\"{a}t in Hagen, Germany}

\begin{keyword} game chromatic number \sep game-perfectness \sep trivially 
perfect \sep graph colouring game
% keywords here, in the form: keyword \sep keyword
\end{keyword}

\end{frontmatter}

% main text
%\section{eins}
%\label{eins}










\section{Introduction}

Consider the following game, played on an (initially uncolored) graph 
$G=(V,E)$ with a color set $C$. 
The players, Alice and Bob, move alternately. 
A move consists in coloring a vertex $v\in V$ with a 
color $c\in C$ in such a way that adjacent vertices receive distinct 
colors. 
If this is not possible any more, the game ends.
Alice wins if every vertex is colored in the end, otherwise Bob wins.

This type of game was introduced by Bodlaender~\cite{bodlaender}. He 
considers a variant, which we will call game~$g$, in which Alice must move 
first and passing is not allowed.
In order to obtain upper and lower bounds for a parameter associated with 
game~$g$, two other variants are useful.
In the game~$B$ Bob may move first.
He may also miss one or several turns, but Alice must always move.
In the other variant, game~$A$, Alice may move first and miss one or 
several turns, but Bob must move.
So in game~$B$ Bob has some advantages, whereas in game~$A$ Alice has some 
advantages with respect to Bodlaender's game. % (see~\cite{andresforest}).

For any variant $\mathcal{G}\in\{B,g,A\}$, the smallest cardinality of a 
color set~$C$, so that Alice has a winning 
strategy for the game $\mathcal{G}$ is called 
\emph{$\mathcal{G}$-game chromatic 
number} $\chi_{\mathcal{G}}(G)$ of~$G$.

%During the last two decades, a lot of work has been done to determine 
%upper bounds for the $g$-game chromatic number of classes of graphs, 
%initiated by the papers of Bodlaender~\cite{bodlaender} and Faigle et 
%al.~\cite{faigleetal}. A recent survey was given by Bartnicki et 
%al.~\cite{bartnickietal}.

Let $\omega(G)$ be the clique number of a graph~$G$. $G$~is called 
\emph{$B$-perfect} if, for any induced subgraph $H$ of~$G$, 
$\chi_B(H)=\omega(H)$. 
Analogously, we define \emph{$A$-perfect} with respect to the game~$A$ and 
\emph{$g$-perfect} with respect to Bodlaender's game.
These concepts were introduced in~\cite{andresgperfect} and are 
game-theoretic analoga of \emph{perfect} graphs which 
are those graphs in which, for any induced subgraph~$H$, the clique number 
equals the chromatic number $\chi(H)$.  
For any graph $H$,
\[\omega(H)\le\chi(H)\le\chi_A(H)\le\chi_g(H)\le\chi_B(H).\]
In particular, $B$-perfect graphs are $g$-perfect, $g$-perfect graphs are 
$A$-perfect, and $A$-perfect graphs are perfect. We consider the problem 
of characterizing these classes of graphs. The (probably 
most difficult) case of perfect graphs has been solved by the
Strong Perfect Graph Theorem~\cite{SPGT}:

\begin{thm}[Chudnovsky, Robertson, Seymour, Thomas 
(2006)]\label{satzSPGT}
A\\ graph is perfect if, and only if, it does neither contain 
an odd hole 
nor an odd antihole as induced subgraph.
\end{thm}


In this talk we will characterize $B$-perfect graphs.



\section{Main result}\label{Bperf}


\begin{thm}\label{main}
Let $G$ be a graph. Then the following conditions are equivalent:
\begin{itemize}
 \item[(i)] $G$ is $B$-perfect.
\item[(ii)] $G$ does {neither contain} a {$C_4$}, nor a {$P_4$}, nor a  
{split 3-star}, nor a {double fan} as induced 
subgraph (see Fig.~\ref{bilde}).
\item[(iii)] For every (nonempty) component $H$ of $G$, there is $k\ge0$, 
so that
\[H=K_1\vee(H_0\cup H_1\cup\ldots\cup H_k),\]
where the {$H_i$ are complete graphs} for $i\ge1$,
 and $H_0$ is either empty or there are $p,q,r\in{\mathbb N}$, so that
$H_0=K_p\vee K_r\vee K_q$ (see Fig.~\ref{bildz}).
\end{itemize}
\end{thm}



\begin{figure}[hbp]
\begin{minipage}[b]{0.24\textwidth}
\begin{center}
\includegraphics[width=0.58\textwidth]{C4s}

$C_4$
\end{center}
\end{minipage}
\begin{minipage}[b]{0.24\textwidth}
\begin{center}
\includegraphics[width=0.8\textwidth]{P4s}

$P_4$
\end{center}
\end{minipage}
\begin{minipage}[b]{0.24\textwidth}
\begin{center}
\includegraphics[width=0.8\textwidth]{split3star}

split 3-star
\end{center}
\end{minipage}
\begin{minipage}[b]{0.24\textwidth}
\begin{center}
\includegraphics[width=0.8\textwidth]{doublefan}

double fan
\end{center}
\end{minipage}
\caption{\label{bilde}4 forbidden induced subgraphs for $B$-perfect 
graphs}
\end{figure}
















\begin{figure}[htbp]
\begin{center}
 \includegraphics[height=0.18\textheight]{generalwheel} %0.25\th
\end{center}
\caption{\label{bildz}Structure of a component according to (iii)}
\end{figure}


\begin{pf}
(i) $\Longrightarrow$ (ii): 
Winning strategies for Bob with $\le2$ colors on 
$C_4$ resp.\ $P_4$ resp.\ with $\le3$ colors on the split 3-star resp.\ 
the 
double fan are obvious.

\bigskip

\noindent
(iii) $\Longrightarrow$ (i):
We describe a winning strategy for Alice with $\omega(G)$ colors on a 
graph $G$ as in (iii).
This is sufficient since every induced subgraph of $G$ is of the same 
type as described in (iii).
For $H_0=K_p\vee K_r\vee K_q$ let the $K_p$ and the $K_q$ be the 
\emph{ears}.
 Alice always responds to Bob's moves in the same component~$H$ (if Bob 
passes, in an arbitrary component).
 As long as Bob does not play in an ear, Alice does not play in an ear; 
she 
 first colors the universal vertex of $H$.
 If Bob plays in an ear $K_p$, Alice colors a vertex in the corresponding 
 ear $K_q$ with the same color (in case there is no uncolored vertex she 
 uses the strategy described before).
 If Alice is forced to start coloring an ear, then all 
 non-ear-vertices are colored, so a coloring of the ears is possible 
 without creating danger for a non-ear-vertex.

\bigskip

(ii) $\Longrightarrow$ (iii):
We examine the structure of a graph $G$ without induced $P_4$, $C_4$, 
split 3-star, double fan.
Let $H$ be a component of $G$.
We use the following lemma of Wolk~\cite{wolk}.

\begin{lem}[Wolk (1965)]\label{wolklemma}
A connected graph without induced $C_4$ and $P_4$ (a so-called 
\emph{trivially perfect graph~\cite{golumbic}}) has a universal vertex.
\end{lem}

So, $H$ has a universal vertex $v$.
Let $H_0,\ldots,H_n$ be the components of~$H\setminus v$.
Using the fact that $H$ does not contain a double fan we can prove the 
following

\begin{claim}\label{vorcl}
At most one of the $H_i$ is not complete.
\end{claim}




Let $H_0$ be the (only) component of $H\setminus v$ which is not complete.
Let $K$ be the largest clique of $H_0$.
We are done if we show:

\begin{claim}\label{clzwei}
$H_0\setminus K$ induces a clique.
\end{claim}

\begin{claim}\label{cleins}
$H_0\setminus K$ induces a module of $H_0$
(i.e.\ if $x\in K$, either $x$ is adjacent to all $y\in H_0\setminus K$ or to none.)
\end{claim}

The proof of Claim~\ref{clzwei} uses Lemma~\ref{wolklemma} again and the 
fact that $H$ does neither contain a split 3-star nor a $P_4$.
The proof of Claim~\ref{cleins} uses Claim~\ref{clzwei} and the fact that 
$H$ does neither contain a $P_4$ nor a $C_4$.

Claim~\ref{vorcl}, Claim~\ref{clzwei} and Claim~\ref{cleins} together 
imply that $H$ has the 
structure as described in (iii):
$H_0\setminus K$ corresponds to the $K_p$, its neighbors 
correspond to the $K_r$, and the rest of $H_0$ corresponds to the 
$K_q$.
This completes the proof of Theorem~\ref{main}.\hfill$\Box$
\end{pf}








\section{Open problems}


\begin{prob}
Characterize $A$-perfect graphs by forbidden induced subgraphs. % and/or 
%explicitly.
\end{prob}


\begin{prob}
Characterize $g$-perfect graphs by forbidden induced subgraphs. % and/or 
%explicitly.
\end{prob}

We discuss some partial results concerning these problems.
%characterization of 
%$A$-perfect and $g$-perfect graphs.
The following are already known, cf.~\cite{andresgperfect}:









\begin{thm}
A {triangle-free} graph $G$ is {$A$-perfect} if, and only if, 
{every component} of $G$ is either {$K_1$} or {$K_{m,n}$} or 
{$K_{m,n}-e$}, where $e$ is an edge.
\end{thm}

\begin{thm}
Complements of bipartite graphs are $A$-perfect.
\end{thm}









\begin{thebibliography}{00}
\bibitem{andresgperfect}
Andres, S.\ D.,
\emph{Game-perfect graphs},
Math.\ Meth.\ Oper.\ Res.\ {\bf 69} (2009), 235--250


\bibitem{bodlaender}
Bodlaender, H.\ L.,
\emph{On the complexity of some coloring games},
Int.\ J.\ Found.\ Comput.\ Sci.\ {\bf 2}, no.2 (1991), 133--147


\bibitem{SPGT}
Chudnovsky, M., N.\ Robertson, P.\ Seymour, and R.\ Thomas,
\emph{The strong perfect graph theorem},
Ann.\ Math.\ {\bf 164} (2006), 51--229

\bibitem{golumbic}
Golumbic, M.\ C.,
\emph{Trivially perfect graphs},
Discrete Math.\ {\bf 24} (1978), 105--107

\bibitem{wolk}
Wolk, E.\ S.,
\emph{A note on ``the comparability graph of a tree''},
Proc.\ Am.\ Math.\ Soc.\ {\bf 16} (1965), 17--20


\end{thebibliography}




\end{document}
















