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