% 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}

% 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}

\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{On Reed's Conjecture in Triangle-Free Graphs}

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

\author{Vera Weil}
\ead{weil@zpr.uni-koeln.de}
\address{Institut f\"{u}r Informatik, Arbeitsgruppe Faigle/Schrader (AFS),\\
	University of Cologne, Weyertal 80, 50931 Cologne, Germany}

\begin{keyword}
Coloring \sep Reed's Conjecture \sep Minimal Counterexample \sep Triangle-Free Graphs
% keywords here, in the form: keyword \sep keyword
\end{keyword}

\end{frontmatter}

% main text
\section{Introduction}
The problem of finding the chromatic number of a graph $G$, i.e. the minimum number of colors needed to
assign distinct colors to adjacent nodes of $G$, is NP-complete. 
However, there are some known bounds including the trivial lower bound 
$$\chi(G) \geq \omega(G)$$ and the upper bound provided by Brooks \cite{Brooks} $$\chi(G) \leq \Delta(G) + 1,$$ where $\chi(G)$ denotes the chromatic 
number, $\Delta(G)$ the maximum degree and $\omega(G)$ the number of nodes of a largest clique in $G$.

In \cite{Reed}, Reed conjectured that $$\chi(G) \leq \left\lceil \frac{\Delta(G) + 1 + \omega(G)}{2} \right\rceil.$$
Note that this upper bound rounds up the arithmetic average of the previous mentioned upper and lower bounds.

In the following all graphs are simple, undirected and connected.
$V(G)$ and $E(G)$ denote the nodes and edges of $G$ respectively.
The degree of $v \in V(G)$ ($deg(v)$) gives the number of neighbors of $v$ in $G$. 

%\section{Graph classes for which the conjecture holds}
Reed \cite{Reed} proved the existence of a constant $\Delta_0$ so that the conjecture holds for graphs 
with $\Delta(G) \geq \Delta_0$ and 
\mbox{$\omega(G) \geq \lfloor (1 - \frac{1}{70000000})\Delta(G)\rfloor$.} 

Other graph classes for which the validity of Reed's conjecture could be shown have been found, among them 
the classes listed in Proposition \ref{A1}. This list consists of graph classes for which the 
conjecture follows straightforward from their definition or for which other authors (sources given in parantheses) have shown the conjecture holds. 

%We give a list of further graph classes (needless to say this list won't be exhaustive), for which 
%the validity of Reed's conjecture could be shown. This list consists predominantly of graph classes for which the 
%conjecture follows straightforward from their definition or for which other authors (sources given in parantheses) have shown the conjecture holds. 
\begin{prop}\label{A1}%[list of graph classes]
For the following graphs the conjecture holds:
\begin{itemize} 
\item complete graphs 
\item perfect graphs
\item circles
\item graphs with size of maximum independent set $\alpha(G)=2$ (\cite{Molloy})
\item line graphs (\cite{King})
\item triangle-free graphs with minimum degree $\delta(G) \geq \frac{n}{3}$ (\cite{Brandt}) 
\item triangle-free graphs with chromatic number $\chi(G) \leq 4$ (consequence of Brooks' theorem)
\end{itemize}
\end{prop}

%\section{Results for a minimal triangle-free counterexample}
In this work we focus on triangle-free graphs ($\omega(G)=2$), 
for which Reed's conjecture reads as follows:%so that we can formulate Reed's conjecture as follows:
$$\chi(G) - 1\leq \left\lceil \frac{\Delta(G) + 1}{2}\right\rceil.$$ 

In order to investigate the conjecture we search for a triangle-free counterexample with a minimum number of nodes. 


%As the prevailing investigation method to prove or disprove the conjecture we search for a triangle-free counterexample of minimal order.
Gathering properties of a minimal order counterexample, we can continue a list already 'started' in \cite{Gernert}.
Some of these properties turn out to be quite fruitful, in particular the fact that a minimal counterexample has to be vertex-color-critical, i.e. 
$\chi(G-v) < \chi(G)$ for any vertex $v$ of $G$. 

\begin{defn}[heavy edge]
Let $G$ be a graph. Then we call $(x,y) \in E(G)$ a heavy edge if $deg(x)=deg(y)=\Delta(G)$.
\end{defn}

\begin{defn}[heavy circle]
Let $G$ be a graph and $C \subseteq V(G)$ a circle of $G$. 
We call $C$ a heavy circle if $$v \in V(C) \Rightarrow deg(v) \geq \Delta(G)-2.$$
\end{defn}


\section{Results}

%We prove that in a minimal counterexample, the maximal degree $\Delta(G) = 2\chi(G) - 5$; furthermore there exists a "heavy edge" %, i.e. an edge whose endnodes are both of maximal degree, 
%and a "heavy circle". %, in which all vertices are at least of degree $\Delta(G) - 3$.

\begin{thm}
Let $G$ be a triangle-free minimal counterexample to Reed's conjecture.
Then $\Delta(G) = 2\chi(G) - 5$. 
\end{thm}

\begin{thm}
Let $G$ be a triangle-free minimal counterexample to Reed's conjecture.
Then there exists at least one heavy edge. % $(x,y)$ in $E(G)$ with $deg(x) = deg(y) = \Delta(G)$.
\end{thm}

\begin{thm}
Let $G$ be a triangle-free minimal counterexample to Reed's conjecture. 
Then there exists at least one heavy circle $C$ of odd length. %with $$v \in V(C) \Rightarrow deg(v) \geq \Delta(G) - 2.$$
\end{thm}
Moreover, we describe a construction  which embeds  an arbitrary triangle-free graph $G$
in a regular triangle-free graph preserving $\chi(G)$ and $\Delta(G)$. From this we get that it suffices to prove Reed's conjecture
for regular triangle-free graphs. 
\begin{thm}
If Reed's conjecture holds for all regular triangle-free graphs, it holds for all triangle-free graphs.  
\end{thm}


\begin{thebibliography}{00}
\bibitem{Brandt} S. Brandt, S. Thomass\'{e} (2005): {\itshape Dense triangle-free graphs are four-colorable: A solution to the Erd\"{o}s-Simonovits problem.}
To appear in Journal of Combinatorial Theory B.\\http://www.lirmm.fr/~thomasse/liste/vega11.pdf
\bibitem{Brooks} R.L. Brooks (1941): {\itshape On colouring the nodes of a network.} Proceedings of the Cambridge Philosophical Society 37, 194 - 197.
\bibitem{Gernert} D. Gernert, L. Rabern (2007): {\itshape A knowledge-based system for graph theory, demonstrated by partial proofs for graph coloring problems.} MATCH Commun. Math. Comput. Chem., Vol. 58, 445 - 460.
\bibitem{King} A.D. King, B.A. Reed, A. Vetta (2007): {\itshape An upper bound for the chromatic number of line Graphs}. European Journal Of Combinatorics, Vol. 28(8), 
2182-2187.
\bibitem{Molloy} M. Molloy (1991): {\itshape Chromatic neighbourhood sets}. Journal Of Graph Theory, Vol. 31, 303 - 311. 
\bibitem{Reed} B. Reed (1998): {\itshape $\omega$,$\Delta$ and $\chi$ (OMEGA, DELTA AND CHI)}. Journal Of Graph Theory, Vol. 27, 177 - 212. 


% \bibitem{label}
% Text of bibliographic item

% notes:
% \bibitem{label} \note

% subbibitems:
% \begin{subbibitems}{label}
% \bibitem{label1}
% \bibitem{label2}
% If there is a note, it should come last:
% \bibitem{label3} \note
% \end{subbibitems}



\end{thebibliography}

\end{document}

