\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P2.1}{22(2)}{2015}

\usepackage{amsmath, amsthm, amssymb}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
\usepackage{verbatim}
%\usepackage[top=1.0in, bottom=1.0in, left=1.0in, right=1.0in]{geometry}

\pagestyle{plain}

\usepackage{tkz-graph}
\usetikzlibrary{arrows}
\usetikzlibrary{shapes}
\usepackage[position=bottom]{subfig}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}


%\usepackage{longtable}
%\usepackage{array}

\usepackage{sectsty}
%\allsectionsfont{\sffamily}

\setcounter{secnumdepth}{5}
\setcounter{tocdepth}{5}

\makeatletter
\newtheorem*{rep@theorem}{\rep@title}
\newcommand{\newreptheorem}[2]{
\newenvironment{rep#1}[1]{
 \def\rep@title{#2 \ref{##1}}
 \begin{rep@theorem}}
 {\end{rep@theorem}}}
\makeatother

\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newreptheorem{thm}{Theorem}
\newtheorem{prop}[thm]{Proposition}
\newreptheorem{prop}{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newreptheorem{lem}{Lemma}
\newtheorem{conjecture}[thm]{Conjecture}
\newreptheorem{conjecture}{Conjecture}
\newtheorem{cor}[thm]{Corollary}
\newreptheorem{cor}{Corollary}
\newtheorem{prob}[thm]{Problem}
\newtheorem{observation}{Observation}
\newtheorem*{mainconj}{Main Conjecture}
\newtheorem*{mainthm}{Main Theorem}

%\newtheorem*{SmallPotLemma}{Small Pot Lemma}
%\newtheorem*{BK}{Borodin--Kostochka Conjecture}
%\newtheorem*{BK2}{Borodin--Kostochka Conjecture (restated)}
%\newtheorem*{Reed}{Reed's Conjecture}
%\newtheorem*{ClassificationOfd0}{Classification of $d_0$-choosable graphs}


\theoremstyle{definition}
\newtheorem{defn}{Definition}
\theoremstyle{remark}
\newtheorem*{remark}{Remark}
\newtheorem*{problem}{Problem}
\newtheorem{example}{Example}
\newtheorem*{question}{Question}


\newcommand{\fancy}[1]{\mathcal{#1}}
\newcommand{\C}[1]{\fancy{C}_{#1}}
\newcommand{\IN}{\mathbb{N}}
\newcommand{\IR}{\mathbb{R}}
\newcommand{\G}{\fancy{G}}
\newcommand{\CC}{\fancy{C}}
\newcommand{\D}{\fancy{D}}

%\newcommand{\inj}{\hookrightarrow}
%\newcommand{\surj}{\twoheadrightarrow}

\newcommand{\set}[1]{\left\{ #1 \right\}}
%\newcommand{\setb}[3]{\left\{ #1 \in #2 \mid #3 \right\}}
%\newcommand{\setbs}[2]{\left\{ #1 \mid #2 \right\}}
\newcommand{\card}[1]{\left|#1\right|}
%\newcommand{\size}[1]{\left\Vert#1\right\Vert}
\newcommand{\ceil}[1]{\left\lceil#1\right\rceil}
\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}
%\newcommand{\func}[3]{#1\colon #2 \rightarrow #3}
%\newcommand{\funcinj}[3]{#1\colon #2 \inj #3}
%\newcommand{\funcsurj}[3]{#1\colon #2 \surj #3}
%\newcommand{\irange}[1]{\left[#1\right]}
\newcommand{\irange}[1]{\{1,\ldots,#1\}}
%\newcommand{\join}[2]{#1 \mbox{\hspace{2 pt}$\ast$\hspace{2 pt}} #2}
%\newcommand{\djunion}[2]{#1 \mbox{\hspace{2 pt}$+$\hspace{2 pt}} #2}
\newcommand{\parens}[1]{\left( #1 \right)}
\newcommand{\brackets}[1]{\left[ #1 \right]}
%\newcommand{\nint}[1]{\widetilde{N}\left(#1\right)}
\newcommand{\DefinedAs}{\mathrel{\mathop:}=}

%\def\adj{\leftrightarrow}
%\def\nonadj{\not\!\leftrightarrow}

%\def\D{\fancy{D}}
\def\C{\fancy{C}}
\def\Q{\fancy{Q}}
\def\Z{\fancy{Z}}

%\newcommand{\bigclique}[1]{\frac{2}{3}\Delta(#1) + 5}
%\newcommand{\bigcliqueraw}{\frac{2}{3}\Delta + 5}
%\newcommand{\cliqueparts}{\frac{2}{3}\Delta}

% any changes to \claim should be mirrored in \claimnonum and \subclaim
%\newcommand{\claim}[2]{{\bf Claim #1.}~{\it #2}~~}
%\newcommand{\claimnonum}[1]{{\bf Claim.}~{\it #1}~~}
%\newcommand{\subclaim}[2]{{\bf Subclaim #1.}~{\it #2}~~}


\date{\dateline{Aug 24, 2014}{Mar 18, 2015}{Apr 14, 2015}\\
\small Mathematics Subject Classifications: 05C15, 05C69}



\begin{document}
\title{\bf
A note on coloring vertex-transitive graphs
}
\author{Daniel W. Cranston\thanks{Department of Mathematics and Applied
Mathematics, Virginia Commonwealth University, Richmond, VA, 23284, U.S.A.\
\texttt{dcranston@vcu.edu}} \and 
Landon Rabern\thanks{Lancaster, PA, 17601, U.S.A.\ 
\texttt{landon.rabern@gmail.com} 
}}
\maketitle
\date

\begin{abstract}
We prove bounds on the chromatic number $\chi$ of a vertex-transitive graph in
terms of its clique number $\omega$ and maximum degree $\Delta$. We conjecture
that every vertex-transitive graph satisfies $\chi \le \max \{\omega,
\left\lceil\frac{5\Delta + 3}{6}\right\rceil\}$, and we prove results supporting
this conjecture.  Finally, for vertex-transitive graphs with $\Delta \ge 13$ we
prove the Borodin--Kostochka conjecture, i.e., $\chi\le\max\{\omega,\Delta-1\}$.

  \bigskip\noindent \textbf{Keywords:} graph coloring, vertex transitive, Borodin--Kostochka conjecture

\end{abstract}

%We prove bounds on the chromatic number $\chi$ of a vertex-transitive graph in
%terms of its clique number $\omega$ and maximum degree $\Delta$.  We conjecture
%that every vertex-transitive graph satisfies $\chi \le \max \set{\omega,
%\ceil{\frac{5\Delta + 3}{6}}}$ and we prove results supporting this conjecture. 
%Finally, for vertex-transitive graphs with $\Delta \ge 13$
%we prove the Borodin--Kostochka conjecture, i.e.,
%$\chi\le\max\set{\omega,\Delta-1}$.
%\end{abstract}

\section{Introduction}
Many results and conjectures in the graph coloring literature have the
form: \emph{if the chromatic number $\chi$ of a graph is close to its maximum
degree $\Delta$,
then the graph contains a big clique, i.e., $\omega$ is large}
(\cite{brooks1941colouring,
borodin1977upper, reed1999strengthening, reed1998omega, CatlinAnotherBound,
molloy2002graph}). Generically, we call conjectures of this sort \emph{big
clique conjectures}.  In
\cite{denseneighborhoods}, it was shown that many big clique conjectures 
hold under the added hypothesis that every vertex is in a medium sized clique. 
Partial results on big clique conjectures often guarantee a medium sized clique,
but not a big clique.  But in a vertex-transitive graph, the existence of one
medium sized clique implies that every vertex is in a medium sized clique.
By applying the idea in \cite{denseneighborhoods}, we now get a big clique. 
So, in essence, partial results on big clique conjectures are
self-strengthening in the class of vertex-transitive graphs.

In this short note, we give some examples of this phenomenon.  
Basically, we are combining some known results to yield some interesting
consequences that we previously did not know.
%There is not much new graph theory here, just combinations of known results
%that yield facts we did not know.  
The following conjecture is the best we could hope for. 
A good deal of evidence supports it, as we will detail below.

\begin{mainconj}
%\label{MainConjecture}
If $G$ is vertex-transitive, then $\chi(G) \le \max \set{\omega(G), \ceil{\frac{5\Delta(G) + 3}{6}}}$.
\end{mainconj}

Our Main Conjecture would be best possible, as shown by Catlin's
counterexamples to the Haj{\'o}s conjecture \cite{catlin1979hajos}.  Catlin
computed the chromatic number of line graphs of odd cycles where each edge has
been duplicated $k$ times; in particular, he showed that $\chi(G_{t,k}) = 2k +
\ceil{\frac{k}{t}}$ for $t \ge 2$, where $G_{t,k}$ is this line graph, i.e.,
$G_{t,k} \DefinedAs L(kC_{2t+1})$.  Since $\Delta(G_{t,k}) = 3k-1$ and
$\omega(G_{t,k}) = 2k$, we have $\chi(G_{2, k}) = 2k+\ceil{\frac{k}2} =
\ceil{\frac{5k}2} = \ceil{\frac{15k-2}6} = \max \set{\omega(G_{2,k}),
\ceil{\frac{5\Delta(G_{2,k}) + 3}{6}}}$ for all $k \ge 1$.

Our main result is the following weakening of the Borodin--Kostochka conjecture
for vertex-transitive graphs, which we prove in Section~\ref{BK}.  This theorem
likely holds for all $\Delta \ge 9$ and proving this may be a good deal easier
than proving the full Borodin--Kostochka conjecture (note that the Main
Conjecture implies the Main Theorem, so our proof of the theorem should weigh
as evidence in support of the conjecture).

\begin{mainthm} %\label{BKTransitive}
If $G$ is vertex-transitive with $\Delta(G) \ge 13$ and $K_{\Delta(G)} \not \subseteq G$, then $\chi(G) \le \Delta(G) - 1$.
\end{mainthm}

As further evidence for the Main Conjecture, we show that the analogous upper
bound holds for the fractional chromatic number.  Also, we show that the Main
Conjecture is true if all vertex-transitive graphs satisfy both Reed's
$\omega$, $\Delta$, and $\chi$ conjecture and the strong $2\Delta$-colorability
conjecture (see \cite{aharoni2007independent}; really we can get by with
$\frac52\Delta$-colorability).  Finally, we show the following.

\begin{thm}
There exists $c < 1$, such that for any vertex-transitive graph $G$, we have $\chi(G) \le \max \set{\omega(G), c(\Delta(G) + 1)}$.
\end{thm}

\section{Clustering of maximum cliques}
Before coloring anything, we need a better understanding of the structure of maximum cliques in a graph.
\subsection{The clique graph}
\begin{defn}
Let $G$ be a graph. For a collection of cliques $\Q$ in $G$, let $X_\Q$ be the
intersection graph of $\Q$; that is, the vertex set of $X_\Q$ is $\Q$ and there
is an edge between $Q_1, Q_2 \in \Q$ if and only if $Q_1 \ne Q_2$ and $Q_1$ and $Q_2$ intersect.
\end{defn}

When $\Q$ is a collection of maximum cliques, we get a lot of information about
$X_\Q$.  Kostochka \cite{kostochkaRussian} used the following lemma of Hajnal
\cite{HajnalSaturation} to show that the components of $X_\Q$ are complete in a
graph with $\omega > \frac23 (\Delta + 1)$.

\begin{lem}[Hajnal \cite{HajnalSaturation}]\label{HajnalLemma}
If $G$ is a graph and $\Q$ is a collection of maximum cliques in $G$, then 
\[\card{\bigcup \Q} + \card{\bigcap \Q} \geq 2\omega(G).\]
\end{lem}

Hajnal's lemma holds by an easy induction.  The proof of Kostochka's lemma in
\cite{kostochkaRussian} is in Russian; for a reproduction of his original proof
in English, see \cite{rabernhitting}.  Below we give a shorter proof from
\cite{raberndiss}.

\begin{lem}[Kostochka \cite{kostochkaRussian}]\label{KostochkaCliqueGraph}
If $\Q$ is a collection of maximum cliques in a graph $G$ with $\omega(G) >
\frac23 (\Delta(G) + 1)$ such that $X_\Q$ is connected, then $\cap \Q \neq \emptyset$. 
\end{lem}
\begin{proof}
Suppose not and choose a counterexample $\Q \DefinedAs \set{Q_1, \ldots, Q_r}$
minimizing $r$. Then, plainly, $r \geq 3$. Let $A$ be a noncutvertex in $X_{\Q}$ and
$B$ a neighbor of $A$. Put $\fancy{Z} \DefinedAs \Q \setminus \set{A}$. Now
$X_{\fancy{Z}}$ is connected, so the minimality of $r$ implies that $\cap \fancy{Z}
\neq \emptyset$. In particular, $\card{\cup \fancy{Z}} \leq \Delta(G) + 1$.
Since $A\cap B\ne \emptyset$, we have $|A\cup B|\le \Delta(G)+1$, so
$|A\setminus B|=|A\cup B|-|B|\le \Delta(G)+1-\omega(G)$.
By assumption, $\cap\Q=\emptyset$, so $\card{\cap \Q} + \card{\cup \Q} \leq 0 +
(\card{\cup \fancy{Z}} + \card{A \setminus B}) \leq
(\Delta(G) + 1) + (\Delta(G)+1 - \omega(G)) < 2\omega(G)$; the final inequality
holds by hypothesis.  Hence $\card{\cap \Q}+\card{\cup \Q}<2\omega(G)$, which
contradicts
Lemma \ref{HajnalLemma}.
\end{proof}

As shown by Christofides, Edwards, and King \cite{christofides2012note},
components of $X_\Q$ also have nice structure when $\omega = \frac23 (\Delta +
1)$.  We'll need this stronger result to get our bounds on coloring
vertex-transitive graphs to be tight.

\begin{lem}[Christofides, Edwards, and King \cite{christofides2012note}]\label{TwoThirdsEqualityStructure}
If $\Q$ is a collection of maximum cliques in a graph $G$ with $\omega(G) \ge \frac23 (\Delta(G) + 1)$ such that $X_\Q$ is connected, then either 
\begin{itemize}
\item[(i)] $\cap \Q \ne \emptyset$; or
\item[(ii)] $\Delta(X_\Q) \le 2$ and if $B, C \in \Q$ are different neighbors of $A \in \Q$, then $B \cap C = \emptyset$ and $\card{A \cap B} = \card{A \cap C} = \frac12 \omega(G)$.
\end{itemize}

\end{lem}
\subsection{In vertex-transitive graphs}
A graph is \emph{vertex-transitive} if 
%it ``looks the same'' when viewed from the perspective of every vertex.  Formally, 
for any pair of vertices $u$ and
$v$, there exists an automorphism mapping $u$ to $v$.
Let $G$ be a vertex-transitive graph and let $\Q$ be the collection of all
maximum cliques in $G$.  It is not hard to see that $X_\Q$ is vertex-transitive
as well; in fact, we have the following.

\begin{observation}\label{transitiveClustering}
Let $G$ be a vertex-transitive graph and let $\Q$ be the collection of all
maximum cliques in $G$.  For each component $C$ of $X_\Q$, put $G_C \DefinedAs
G\brackets{\bigcup V(C)}$;  that is, $G_C$ is the subgraph of $G$ induced by all
vertices that appear in cliques in $C$.
Now $G_C$ is vertex-transitive for each component
$C$ of $X_\Q$ and $G_{C_1} \cong G_{C_2}$ for all components $C_1$ and $C_2$ of
$X_\Q$.
\end{observation}

\begin{proof}
Let $C_1$ and $C_2$ be components of $X_Q$ (possibly the same).  If $x \in
V(G_{C_1})$ and $y \in V(G_{C_2})$ and $\tau$ is an automorphism of $G$ with
$\tau(x) = y$, then for every $M \in V(C_1)$ with $x \in M$ we have $\tau(M)
\in V(C_2)$.  Applying this fact repeatedly, we conclude that $\tau(V(G_{C_1}))
\subseteq V(G_{C_2})$.  Since $\tau^{-1}(y) = x$, we get the other inclusion as
well and conclude that $\tau(V(G_{C_1})) = V(G_{C_2})$.  So, the restriction of
$\tau$ to $G_{C_1}$ is an isomorphism from $G_{C_1}$ to $G_{C_2}$.

Since $G$ is vertex-transitive, for any $w,z \in V(G_{C_1})$ we can choose an
automorphism of $G$ mapping $w$ to $z$; the restriction of this automorphism to
$G_{C_1}$ is an automorphism of $G_{C_1}$ mapping $x$ to $y$.  So, $G_{C_1}$ is
vertex-transitive.  Similarly, $G_{C_1}$ is isomorphic to $G_{C_2}$ for any
components $C_1$ and $C_2$ of $X_Q$.
\end{proof}
%\noindent
%Both conclusions follow directly from the fact that $G$ is vertex-transitive.
%
%%%The fact that always $G_{C_1}\cong G_{C_2}$ follows immediately from the fact
%%%that $G$ is vertex-transitive.  The fact that $G_C$ is vertex-transitive also
%%%follows.

Recall that a vertex $v$ in a graph $G$ is \emph{dominating} (or \emph{universal}) if
$N(v)=V(G)\setminus\{v\}$, i.e., all other vertices are adjacent to $v$.
A basic consequence of Observation \ref{transitiveClustering} is that if $G$ is
vertex-transitive and $G_C$ has a dominating vertex, then
every vertex of $G_C$ is dominating; so $G_C$ is a clique, and thus $C$ is an
isolated vertex.  
Using Lemma \ref{TwoThirdsEqualityStructure}, we get a bit more.

\begin{lem}\label{TransitiveClusteringBigCliques}
Let $G$ be a connected vertex-transitive graph and let $\Q$ be the collection
of all maximum cliques in $G$.  If $\omega(G) \ge \frac23 \parens{\Delta(G) +
1}$, then either
\begin{enumerate}
\item[(i)] $X_\Q$ is edgeless; or
\item[(ii)] $X_\Q$ is a cycle and $G$ is the graph obtained from $X_\Q$ by
blowing up each vertex to a copy of $K_{\frac12 \omega(G)}$.
(Note that this requires $\omega(G)=\frac23(\Delta(G)+1)$.)
\end{enumerate}
\end{lem}
\begin{proof}
%If $\omega(G) > \frac23 \parens{\Delta(G) + 1}$, then $X_\Q$ is edgeless as shown above.  
Let $G$ satisfy the hypothesis and define $\Q$ as in the lemma.
%Let $G$ be a vertex-transitive graph with 
First suppose that $\omega(G) > \frac23 (\Delta(G) + 1)$.   
Suppose further that $X_\Q$ has one or more edges.  Lemma
\ref{KostochkaCliqueGraph} implies that $\cap\Q_C$ is
nonempty, where $\Q_C$ is the set of maximum cliques in some component $G_C$
(as defined in Observation~\ref{transitiveClustering}).
%with an edge in $X_{\Q_C}$.
Choose a vertex $v\in\cap\Q_C$, and note that $v$ is adjacent to each vertex
in $G_C$.  Since $G$ is vertex-transitive,
Observation~\ref{transitiveClustering} implies that $G_C$ is too.  Thus, each
vertex of $G_C$ is a dominating vertex in $G_C$; so, in fact, $G_C$ is a
clique, and $X_\Q$ is edgeless.

Now we assume $\omega(G) = \frac23 \parens{\Delta(G) + 1}$.  Let $Z$ be a
component of $X_\Q$ and put $\Z \DefinedAs V(Z)$, that is, the
cliques of $Z$.  By Lemma
\ref{TwoThirdsEqualityStructure}, $\Delta(X_\Z) \le 2$ and if $B, C \in \Z$ are
different neighbors of $A \in \Z$, then $B \cap C = \emptyset$ and $\card{A
\cap B} = \card{A \cap C} = \frac12 \omega(G)$.  By Observation
\ref{transitiveClustering}, $X_\Z$ must be a cycle.  But now every vertex in
$G_Z$ has $\frac12 \omega(G) + \frac12 \omega(G) + \frac12 \omega(G) - 1 =
\Delta(G)$ neighbors in $G_Z$.  Since $G$ is connected, $G_Z = G$.  Hence $X_\Z
= X_\Q$, so $X_\Q$ is a cycle and $G$ is the graph obtained from $X_\Q$ by
blowing up each vertex to a copy of $K_{\frac12 \omega(G)}$.
\end{proof}

\section{The fractional version}
The problem of determining chromatic number can be phrased as an integer
program: we aim to minimize the total number of colors used, subject to the
constraints that (i) each vertex gets colored and (ii) the vertices receiving
each color form an independent set.  To reach a linear program from this
integer program, we relax the constraint that each vertex is colored with a
single color, and instead allow a vertex to be colored with a combination of
colors, e.g., $\frac12$ red and $\frac13$ green and $\frac16$ blue. However, we still
require that the total weight of any color on any clique is at most 1.
The minimum value of this linear program is the \emph{fractional chromatic
number}, denoted $\chi_f$ (see~\cite{ScheinermanUllmanFrac} for a formal
definition and many results on fractional coloring).

The main result of this section, Corollary~\ref{cor1}, is that our Main
Conjecture is true when we replace $\chi(G)$ with $\chi_f(G)$.  Our proof will
need the fact that
every vertex-transitive graph $G$ satisfies
$\chi_f(G) = \frac{|G|}{\alpha(G)}$, where $|G|$ denotes $|V(G)|$ and
$\alpha(G)$ denotes the maximum size of an independent set. 
This is an easy exercise.  For our next lemma,
%For our next proof, 
we need Haxell's condition \cite{haxell2001note} for the
existence of an independent transversal.

\begin{lem}[Haxell \cite{haxell2001note}]
\label{HaxellTransversal}
Let $H$ be a graph and $V_1 \cup \cdots \cup V_r$ a partition of $V(H)$. 
If $\card{V_i} \geq 2\Delta(H)$ for each $i \in \irange{r}$, then $H$
has an independent set $\set{v_1, \ldots, v_r}$
where $v_i \in V_i$ for each $i \in \irange{r}$.
\end{lem}

\begin{lem}\label{TransitiveFractionalColoringWithBigCliques}
If $G$ is a vertex-transitive graph with $\omega(G) \ge \frac23 \parens{\Delta(G) + 1}$, then $\alpha(G) = \floor{\frac{|G|}{\omega(G)}}$.  Moreover, if $\omega(G) > \frac23 \parens{\Delta(G) + 1}$, then $\omega(G)$ divides $|G|$.
\end{lem}
\begin{proof}
We may assume that $G$ is connected, so
Lemma~\ref{TransitiveClusteringBigCliques} applies. Since $G$ is vertex-transitive, every
vertex of $G$ is in an $\omega(G)$-clique. First, suppose that 
Lemma~\ref{TransitiveClusteringBigCliques}.i applies (this includes the
case $\omega(G) > \frac23 \parens{\Delta(G) + 1}$).  
%Then Lemma \ref{TransitiveClusteringBigCliques} shows
Now the vertex set of $G$ can be partitioned into cliques $V_1, \ldots, V_r$
with $|V_i| =\omega(G) \ge \ceil{\frac23 \parens{\Delta(G) + 1}}$ for each $i$. 
%$\in \irange{r}$.  
Let $H$ be the graph formed from $G$ by making each $V_i$
independent.  So $\Delta(H) \le \Delta(G) + 1 - \ceil{\frac23
\parens{\Delta(G) + 1}}$.  Since $|V_i|\ge 2\Delta(H)$, Lemma
\ref{HaxellTransversal} implies that $G$ has
an independent set with a vertex in each $V_i$.  Since 
%$G$ is vertex-transitive, all $V_i$ have the same size; so, in fact, 
$\card{V_i}=\omega(G)$ for all $i$,
we have $\card{G} = \alpha(G)\card{V_i}=\alpha(G)\omega(G)$, so we're done.

%So instead suppose $\omega(G) = \frac23 \parens{\Delta(G) + 1}$.  
So assume instead that Lemma
\ref{TransitiveClusteringBigCliques}.ii applies.
Now $G$ is obtained from a cycle
$C$ by blowing up each vertex of $C$ to a copy of $K_{\frac12 \omega(G)}$. 
Hence $\alpha(G) = \floor{\frac{|C|}{2}} = \floor{\frac{|G|}{\omega(G)}}$ as
desired.
\end{proof}

Reed's $\omega$, $\Delta$, and $\chi$ conjecture proposes that every graph
satisfies 
\[\chi \leq\ceil{\frac{\omega + \Delta + 1}{2}}.\]

In \cite{molloy2002graph}, Molloy and Reed proved that
$\chi_f\le\frac{\omega+\Delta+1}2$; recall that $\chi_f$ is the fractional
chromatic number.
Since $\chi_f(G) = \frac{|G|}{\alpha(G)}$ for vertex-transitive graphs, an
earlier result of Fajtlowicz \cite{fajtlowicz1984independence} suffices for our
purposes.

\begin{lem}[Fajtlowicz \cite{fajtlowicz1984independence}]\label{fajtlowicz}
Every graph $G$ has $\alpha(G) \ge \frac{2|G|}{\omega(G) + \Delta(G) + 1}$.
\end{lem}

\begin{thm}
If $G$ is vertex-transitive, then $\alpha(G) \ge \frac{|G|}{\max\set{\omega(G), \frac56\parens{\Delta(G) + 1}}}$.
\label{fracversion}
\end{thm}
\begin{proof}
If $\omega(G) > \frac23 \parens{\Delta(G) + 1}$, then Lemma
\ref{TransitiveFractionalColoringWithBigCliques} gives $\alpha(G) =
\frac{|G|}{\omega(G)}$ and we're done.  Otherwise, $\omega(G) \le \frac23
\parens{\Delta(G) + 1}$ and Lemma \ref{fajtlowicz} gives $\alpha(G) \ge
\frac{2|G|}{\frac23 (\Delta(G) + 1) + \Delta(G) + 1} = \frac{|G|}{\frac56
(\Delta(G) + 1)}$ as desired.
\end{proof}

Since $\chi_f=\frac{|G|}{\alpha(G)}$ for vertex-transitive graphs, we can
restate Theorem~\ref{fracversion} in terms of fractional coloring as follows.

\begin{cor}
\label{cor1}
If $G$ is vertex-transitive, then $\chi_f(G) \le \max\set{\omega(G), \frac56\parens{\Delta(G) + 1}}$.
\end{cor}

\section{Reed's conjecture plus strong coloring}
For a positive integer $r$, a graph $G$ with $\card{G} = rk$ is called
\emph{strongly $r$-colorable} if for every partition of $V(G)$ into parts of
size $r$ there is a proper coloring of $G$ that uses all $r$ colors on each
part.  If $\card{G}$ is not a multiple of $r$, then $G$ is strongly
$r$-colorable if and only if the graph formed by adding $r\ceil{\frac{|G|}{r}} - |G|$
isolated vertices to $G$ is strongly $r$-colorable.  The \emph{strong chromatic
number} $s\chi(G)$ is the smallest $r$ for which $G$ is strongly $r$-colorable.
Not surprisingly, if $G$ is strongly $r$-colorable, then $G$ is also strongly
$(r+1)$-colorable, although the proof of this fact is
non-trivial~\cite{Fellows1990}.

In \cite{haxell2004strong}, Haxell proved that the strong chromatic number of
every graph is at most $3\Delta - 1$.  We will need this result to prove our
Main Theorem, so we record it here.

\begin{thm}[Haxell \cite{haxell2004strong}]
\label{Haxell3D-1}
Every graph $G$ has strong chromatic number at most $3\Delta-1$.
\end{thm}

In \cite{haxell2008strong}, she proved further that for every $c>\frac{11}4$ there
exists $\Delta_c$ such that if $G$ has maximum degree $\Delta$ at least
$\Delta_c$, then $G$ has strong chromatic number at most $c\Delta$.
The Strong $2\Delta$-colorability conjecture \cite{aharoni2007independent} says
that the strong chromatic number of every graph is at most $2\Delta$.  If true,
this conjecture is sharp. For our next theorem, we need the following
weaker form of the conjecture.

\begin{conjecture}\label{StrongTransitive}
%The strong chromatic number of any vertex-transitive graph is at most $\frac52 \Delta$.
Every vertex-transitive graph has strong chromatic number at most $\frac52 \Delta$.
\end{conjecture}

We also need Reed's conjecture \cite{reed1998omega} restricted to vertex-transitive graphs.

\begin{conjecture}\label{ReedTransitive}
Every vertex-transitive graph satisfies $\chi \leq\ceil{\frac{\omega + \Delta + 1}{2}}$.
\end{conjecture}

\begin{thm}
\label{ConjectureaImplyConjecture}
If Conjectures \ref{StrongTransitive} and \ref{ReedTransitive} both
hold, then so does the Main Conjecture.
\end{thm}
\begin{proof}
We may assume that $G$ is connected. Put $\Delta \DefinedAs \Delta(G)$, $\omega
\DefinedAs \omega(G)$ and $\chi \DefinedAs \chi(G)$. Suppose $\omega < \frac23
\parens{\Delta + 1}$.  So $\omega \le \frac{2\Delta + 1}{3}$ and moreover, when
$\Delta \equiv 3 \text{ (mod $6$)}$, we have $\omega \le \frac23 \Delta$.  
When $\Delta \not\equiv 3 \text{ (mod $6$)}$, 
substituting the first inequality into Conjecture \ref{ReedTransitive}
gives $\chi \le \ceil{\frac{5\Delta + 4}{6}} = \ceil{\frac{5\Delta + 3}{6}}$.
In the remaining case, we have $\omega\le \frac23\Delta$, which
again allows us to prove the desired upper bound
on $\chi$.

Now suppose $\omega \ge \frac23 (\Delta + 1)$ and let $\fancy{Q}$ be the set of
maximum cliques in $G$.  By Lemma \ref{TransitiveClusteringBigCliques},
either $X_\fancy{Q}$ is edgeless or $G$ is obtained from a cycle by
blowing up each vertex to a copy of $K_{\frac{\omega}{2}}$.  If such a cycle is even,
then it is easy to check that $\chi=\omega$.  If the cycle is odd, then
$G$ is one of Catlin's examples from \cite{catlin1979hajos} and the bound holds
as mentioned in the introduction.  Hence we may assume that $X_\fancy{Q}$ is
edgeless; that is, $V(G)$ can be partitioned into $\omega$-cliques
$V_1,\ldots, V_k$.

Suppose $\chi > \omega$. Now we show that Conjecture \ref{StrongTransitive}
implies the Main Conjecture.
Form $G'$ from $G$ by adding vertices to the maximum cliques of $G$ until they
all have $\ceil{\frac{5\Delta + 3}{6}}$ vertices; each new vertex has no edges
outside its clique, and $\Delta$ always denotes the maximum degree in $G$, not
in $G'$. 
Now form $G''$ from $G'$ by removing all edges within each maximum clique.  
%Now $V(G')$ can be partitioned into
Each vertex now has at most $\Delta + 1 - \omega \le
\frac13 (\Delta + 1)$ neighbors in $G'$ outside of its clique;
hence, the maximum
degree of $G''$ is at most $\frac13(\Delta+1)$.  
Since $\ceil{\frac{5\Delta + 3}{6}} \ge
\frac52 \parens{\frac13 (\Delta + 1)}$, Conjecture \ref{StrongTransitive}
implies that $G''$ is strongly 
$\ceil{\frac{5\Delta + 3}{6}}$-colorable.
By taking the maximum cliques $V_i$ as the parts in the partition of of
$V(G'')$, we see that $G'$ is $\ceil{\frac{5\Delta + 3}{6}}$-colorable, and
hence so is $G$.
\end{proof}

Reed \cite{reed1998omega} has shown that there exists some $\epsilon$ with $0 <
\epsilon < 1$ such that
every graph satisfies $\chi \le \epsilon\omega + (1-\epsilon)(\Delta+1)$; for a
shorter and simpler proof, see~\cite{KingReed2012}.  
Using a proof similar to that of Theorem~\ref{ConjectureaImplyConjecture}, we
can combine Reed's upper bound with Haxell's $3\Delta - 1$ strong colorability
result in Lemma~\ref{Haxell3D-1} to get the following Theorem.

\begin{thm}
There exists $c < 1$, such that for every vertex-transitive graph $G$, we have
$\chi(G) \le \max \set{\omega(G), c(\Delta(G) + 1)}$.  Specifically, for any
$\epsilon\in(0,1)$ that satisfies Reed's Theorem, we can let 
$c = \frac{3}{3 + \epsilon}$.
\end{thm}

%Here is the proof of Theorem 4.5.  
\begin{proof}
%Maybe it would be good to state that 
%$c = \frac{3}{3 + \epsilon}$ works given
%$\epsilon \in (0,1)$ such that every graph satisfies $\chi \le \epsilon\omega +
%(1-\epsilon)(\Delta + 1)$.
%
%Theorem.  Vertex-transitive graphs satisfy $\chi \le \max{\omega, \frac{3}{3 +
%\epsilon} (\Delta + 1)}$.
%
If $\omega \le \frac{2 + \epsilon}{3 + \epsilon} (\Delta + 1)$, then Reed's
Theorem gives $\chi\le \epsilon\omega + (1-\epsilon)(\Delta+1) \le
\epsilon\left(\frac{2 + \epsilon}{3 + \epsilon} (\Delta +
1)\right)+(1-\epsilon)(\Delta+1)= \frac{3}{3 + \epsilon} (\Delta + 1)$, so we are done.  
%
Suppose instead that $\omega >  \frac{2 + \epsilon}{3 + \epsilon} (\Delta +
1)$.  As in Theorem~\ref{ConjectureaImplyConjecture}, we conclude from
Lemma~\ref{TransitiveClusteringBigCliques} that $X_Q$ is edgeless.

If $\chi = \omega$, then we are done; so suppose $\chi > \omega$.  
The number of neighbors of each vertex outside of its clique in the partition is
at most $\Delta + 1 - \omega \le \floor{\frac{1}{3 + \epsilon}(\Delta +
1)}$.  Since $\frac{3}{3 + \epsilon}(\Delta+1) \ge 3 \frac{1}{3 + \epsilon}(\Delta + 1) -
1$, we get the coloring bound from Haxell's 3$\Delta-1$ result.
\end{proof}

\section{Borodin--Kostochka for vertex-transitive graphs}
\label{BK}
In \cite{bigcliques}, we proved the following.
\begin{thm}\label{BigCliquesExist}
If $G$ is a graph with $\Delta(G) \ge 13$ and $K_{\Delta(G) - 3} \not \subseteq G$, then $\chi(G) \le \Delta(G) - 1$.
\end{thm} 

In \cite{denseneighborhoods}, the second author proved the following.
\begin{thm}\label{DenseNeighbors}
If $G$ is a graph with $\Delta(G) \ge 9$ and $K_{\Delta(G)} \not \subseteq G$ such that every vertex is in a clique on $\frac23 \Delta(G) + 2$ vertices, then $\chi(G) \le \Delta(G) - 1$.
\end{thm}

By combining Theorems~\ref{BigCliquesExist} and \ref{DenseNeighbors}, we
immediately get that the Borodin--Kostochka conjecture holds for
vertex-transitive graphs with $\Delta \ge 15$, as follows.
Let $G$ be such a graph.  By Theorem~\ref{BigCliquesExist}, if $\chi(G)\ge
\Delta(G)$, then $\omega(G)\ge \Delta(G)-3$.  Since $\Delta(G)\ge 15$, we have
$\omega(G)\ge \Delta(G)-3\ge \frac23\Delta(G)+2$.  Since $G$ is
vertex-transitive, every vertex is in a clique of size $\omega(G)$.  Thus,
Theorem~\ref{DenseNeighbors} implies that $\chi(G)\le \Delta(G)-1$.

We can improve this result to $\Delta \ge 13$ using Lemma
\ref{TransitiveClusteringBigCliques} and
%Haxell's $3\Delta - 1$ strong colorability result, given in
Theorem~\ref{Haxell3D-1}.

\begin{mainthm}\label{BKTransitive}
If $G$ is vertex-transitive with $\Delta(G) \ge 13$ and $K_{\Delta(G)} \not \subseteq G$, then $\chi(G) \le \Delta(G) - 1$.
\end{mainthm}
\begin{proof}
Suppose that $\chi(G)\ge \Delta(G)$.
By Theorem \ref{BigCliquesExist}, we have $\omega(G) \ge \Delta(G) - 3 > \frac23
(\Delta(G) + 1)$ since $\Delta(G) \ge 13$.  
Since this inequality is strict, Lemma
\ref{TransitiveClusteringBigCliques} shows that $X_{\Q}$ is edgeless (here
$\Q$ is the collection of all maximum cliques in $G$), i.e., $G$ can be
partitioned into maximum cliques $V_1,\ldots, V_k$.

Suppose $\chi(G) > \omega(G)$. Form $G'$ from $G$ by adding vertices to the
maximum cliques $V_i$ of $G$ until they all have $\Delta(G) - 1$ vertices, where each
new vertex has no edges outside its clique $V_i$.  Each vertex has at most $\Delta(G)
+ 1 - \omega(G) \le 4$ neighbors outside its clique.  Since $\Delta(G) - 1 \ge 12
\ge 3(4) - 1$, Haxell's $3\Delta - 1$ strong colorability result implies that
$G'$ is $\parens{\Delta(G) - 1}$-colorable and hence so is $G$.
\end{proof}

In fact, Conjecture \ref{ReedTransitive} by itself implies the Borodin--Kostochka
conjecture for vertex-transitive graphs.  Suppose 
%that Conjecture \ref{ReedTransitive} holds, and 
that $G$ is a vertex-transitive counterexample
to the Borodin--Kostochka conjecture.  Since $\chi\ge \Delta$, Conjecture
\ref{ReedTransitive} implies that $\omega \ge \Delta - 2$.
Now whenever $\Delta\ge 9$, we get $\omega\ge  \Delta-2 >
\frac23(\Delta+1)$, so $G$ can again be partitioned into maximum cliques.
%
Similarly, since $\Delta+1-\omega\le 3$, we get $\Delta-1\ge 8 = 3(3)-1$.
Thus, $G$ is $(\Delta-1)$-colorable by Haxell's $3\Delta-1$ strong coloring
result.
%$\frac23 (\Delta + 1)$ when $\Delta \ge 9$.  So, since $\Delta + 1 - \omega \le
%3$, the above argument works for $\Delta \ge 9$.  That is, 

\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}

\begin{thebibliography}{10}

\bibitem{aharoni2007independent}
R.~Aharoni, E.~Berger, and R.~Ziv, \emph{Independent systems of representatives
  in weighted graphs}, Combinatorica \textbf{27} (2007), no.~3, 253--267.

\bibitem{borodin1977upper}
O.V. Borodin and A.V. Kostochka, \emph{{On an upper bound of a graph's
  chromatic number, depending on the graph's degree and density}}, J. Combin.
  Theory Ser. B \textbf{23} (1977), no.~2-3, 247--250.

\bibitem{brooks1941colouring}
R.L. Brooks, \emph{{On colouring the nodes of a network}}, Mathematical
  Proceedings of the Cambridge Philosophical Society, vol.~37, Cambridge Univ
  Press, 1941, pp.~194--197.

\bibitem{CatlinAnotherBound}
P.A. Catlin, \emph{{Another bound on the chromatic number of a graph}},
  Discrete Math. \textbf{24} (1978), no.~1, 1--6.

\bibitem{catlin1979hajos}
\bysame, \emph{Haj{\'o}s' graph-coloring conjecture: variations and
  counterexamples}, J. Combin. Theory Ser. B \textbf{26} (1979), no.~2,
  268--274.

\bibitem{christofides2012note}
D.~Christofides, K.~Edwards, and A.D. King, \emph{A note on hitting maximum and
  maximal cliques with a stable set}, J. Graph Theory \textbf{73} (2013),
  no.~3, 354--360.

\bibitem{bigcliques}
D.W. Cranston and L.~Rabern, \emph{{Graphs with $\chi=\Delta$ have big
  cliques}}, \arxiv{1305.3526} (2013).

\bibitem{fajtlowicz1984independence}
S.~Fajtlowicz, \emph{Independence, clique size and maximum degree},
  Combinatorica \textbf{4} (1984), no.~1, 35--38.

\bibitem{Fellows1990}
M.R. Fellows, \emph{Transversals of vertex partitions in graphs}, SIAM J.
  Discrete Math. \textbf{3} (1990), no.~2, 206--215.

\bibitem{HajnalSaturation}
A.~Hajnal, \emph{{A theorem on $k$-saturated graphs}}, Canad. J. Math.
  \textbf{17} (1965), no.~5, 720.

\bibitem{haxell2001note}
P.E. Haxell, \emph{A note on vertex list colouring}, Combin. Probab. Comput.
  \textbf{10} (2001), no.~4, 345--347.

\bibitem{haxell2004strong}
\bysame, \emph{On the strong chromatic number}, Combin. Probab. Comput.
  \textbf{13} (2004), no.~6, 857--865.

\bibitem{haxell2008strong}
\bysame, \emph{An improved bound for the strong chromatic number}, J. Graph
  Theory \textbf{58} (2008), no.~2, 148--158.

\bibitem{KingReed2012}
A.D. King and B.A. Reed, \emph{{A short proof that $\chi$ can be bounded
  $\epsilon$ away from $\Delta+1$ towards $\omega$}}, J. Graph Theory, to
  appear. Available at: \arxiv{1211.1410}.

\bibitem{kostochkaRussian}
A.V. Kostochka, \emph{{Degree, density, and chromatic number}}, Metody
  Diskretn. Analiz \textbf{35} (1980), 45--70 (in Russian).

\bibitem{molloy2002graph}
M.S. Molloy and B.A. Reed, \emph{{Graph Colouring and the Probabilistic
  Method}}, Springer Verlag, 2002.

\bibitem{rabernhitting}
L.~Rabern, \emph{{On hitting all maximum cliques with an independent set}}, J.
  Graph Theory \textbf{66} (2011), no.~1, 32--37.

\bibitem{raberndiss}
\bysame, \emph{{Coloring Graphs from Almost Maximum Degree Sized Palettes}},
  Arizona State University, 2013.

\bibitem{denseneighborhoods}
\bysame, \emph{Coloring graphs with dense neighborhoods}, J. Graph Theory
  (2013).

\bibitem{reed1998omega}
B.~Reed, \emph{{$\omega$, $\Delta$, and $\chi$}}, J. Graph Theory \textbf{27}
  (1998), no.~4, 177--212.

\bibitem{reed1999strengthening}
\bysame, \emph{{A strengthening of Brooks' theorem}}, J. Combin. Theory Ser. B
  \textbf{76} (1999), no.~2, 136--149.

\bibitem{ScheinermanUllmanFrac}
E.R. Scheinerman and D.H. Ullman, \emph{{Fractional Graph Theory}},
  Wiley-Interscience Series in Discrete Mathematics and Optimization, John
  Wiley \& Sons, Inc., New York, 1997, A rational approach to the theory of
  graphs, With a foreword by Claude Berge, A Wiley-Interscience Publication.

\end{thebibliography}

\end{document}
