% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P4.32}{24(4)}{2017}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed;
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf A note on chromatic number and induced odd cycles}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address

\author{Baogang  Xu\thanks{Research partially supported by NSFC projects 11331003 and 11571180, and by a project funded by PAPD of Jiangsu Higher Education Institutions.}\\
\small Institute of Mathematics, School of Mathematical Sciences\\[-0.8ex]
\small Solatido College\\[-0.8ex]
\small Nanjing Normal University, 1 Wenyuan Road,  Nanjing, 210023,  China\\
\small\tt baogxu@njnu.edu.cn OR baogxu@hotmail.com\\
\and
Gexin Yu\\
\small Department of Mathematics, The College of William and Mary,\\[-0.8ex]
\small Williamsburg, VA, 23185, USA\\[-0.8ex]
\small School of Mathematics and Statistics, Huazhong Normal University, Wuhan, China\\
\small\tt gyu@wm.edu\\
\and 
Xiaoya Zha\\
\small Department of Mathematical Sciences\\[-0.8ex]
\small Middle Tennessee State University, Murfreesboro, TN 37132, USA\\[-0.8ex]
\small\tt xzha@mtsu.edu
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Sep 8, 2015}{Oct 13, 2017}{Nov 3, 2017}\\
\small Mathematics Subject Classifications: 05C15, 05C17,  05C69}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
  An odd hole is an induced odd cycle of length at least 5. Scott and Seymour confirmed a conjecture of Gy\'{a}rf\'{a}s and proved that if a graph $G$ has no odd holes then $\chi(G)\le 2^{2^{\omega(G)+2}}$. Chudnovsky, Robertson, Seymour and Thomas showed that if $G$ has neither $K_4$ nor odd holes then $\chi(G)\le 4$. In this note, we show that if a graph $G$ has neither triangles nor quadrilaterals,  and has no odd holes of length at least 7, then $\chi(G)\le 4$ and $\chi(G)\le 3$ if $G$ has radius at most $3$, and for each vertex $u$ of $G$, the set of vertices of the same distance to $u$ induces a bipartite subgraph. This  answers some questions in \cite{MPXZ}.
  

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} chromatic number; induced odd cycles
\end{abstract}

\section{Introduction}

Let $G$ be a graph, and let $k$ be an integer. A $k$-{\em coloring} of $G$ is an assignment of $k$ colors to the vertices of $G$ such that adjacent vertices receive distinct colors. The {\em chromatic number} $\chi(G)$ of $G$ is the minimum integer $k$ such that $G$ admits a $k$-coloring.
We use $\omega(G)$ to denote the {\em clique number} of $G$ which is the largest integer $l$ such that $G$ contains the complete graph $K_l$ as a subgraph. It is certain that $\chi(G)\ge \omega(G)$. But the difference $\chi(G) - \omega(G)$ may be arbitrarily large as there are triangle-free graphs with arbitrary large chromatic number (see \cite{BD1947, AAZ1949,JM1955}), and furthermore, Erd\H{o}s \cite{PE1959} showed that for every positive integers $k$ and $l$ there exists a graph $G$ with $\chi(G)\ge k$ whose shortest cycle has length at least $l$.

There are still quite a lot of families of graphs whose chromatic numbers are bounded by a function of their  clique numbers. For instance, the {\em Strong Perfect Graph Theorem} \cite{CRST2006} asserts that $\chi(G)=\omega(G)$ if $G$ contains neither odd cycles of length at least 5 nor their complements as induced subgraphs, and Vizing's theorem \cite{vizing1} together with Beineke's characterization \cite{beineke1} shows that $\chi(G)\le \omega(G)+1$ if $G$ contains none of the nine given graphs as induced subgraphs. As a natural question, one may ask, for a given family of graphs ${\cal G}$, whether there is a function $f$ such that $\chi(G)\le f(\omega(G))$ for each graph $G\in {\cal G}?$ If such a function $f$ does exist, then we say that the family ${\cal G}$ is $\chi$-{\em bounded},  and call $f$ a {\em binding function} of ${\cal G}$. In this literature, the family of perfect graphs is $\chi$-bounded with a binding function $f(x)=x$, and the family of line graphs is $\chi$-bounded with a binding function $f(x)=x+1$.

For convenience, we say that a graph $G$ induces a graph $H$ if $H$ is isomorphic to an induced subgraph of $G$. Let ${\cal F}$ be a family of graphs. A graph $G$ is said to be ${\cal F}$-{\em free} if it induces no member of ${\cal F}$. For a finite family ${\cal F}$, Erd\H{o}s \cite{PE1959} shows that if ${\cal F}$-free graphs are $\chi$-bounded then ${\cal F}$ must contain a tree. Then, Gy\'{a}rf\'{a}s \cite{gyarfas1}, and Sumner \cite{sumner1} independently, conjectured that $F$-free graphs are $\chi$-bounded for every forest $F$. There are some partial results about this conjecture (see \cite{CPST2013, gyarfas1987, gyarfas2, kierstead1, KZ2004, scott1}).

A {\em hole} of a graph is an induced cycle of length at least four. Gy\'{a}rf\'{a}s \cite{gyarfas1987} also proposed three conjectures on the relation between chromatic number and induced cycles in graphs.  Let $l$ be an integer of at least $4$.
\begin{conjecture}\label{conj-1}{\em(\cite{gyarfas1987})}
\{odd holes\}-free graphs are $\chi$-bounded.
\end{conjecture}
\begin{conjecture}\label{conj-2}{\em(\cite{gyarfas1987})}
\{holes of length at least $l$\}-free graphs are $\chi$-bounded.
\end{conjecture}
\begin{conjecture}\label{conj-3}{\em(\cite{gyarfas1987})}
\{odd holes of length at least $l$\}-free graphs are $\chi$-bounded.
\end{conjecture}


Scott \cite{scott1999} proved that for each  $l>0$, the family of graphs with neither odd holes nor hole of length at least $l$ is $\chi$-bounded. Chudnovsky, Robertson, Seymour and Thomas \cite{MRST2010} confirmed Conjecture~\ref{conj-1} on graphs of clique number at most 3 and  showed that if $G$ is $\{K_4, odd\ holes\}$-free, then $\chi(G)\le 4$ (note that if $G$ is $\{K_3, odd\ holes\}$-free, then it is bipartite).

In 2016, Scott and Seymour \cite{SS2015} proved that
$\chi(G)\le 2^{2^{\omega(G)+2}}$  for \{odd\  holes\}-free graph $G$ and thus confirmed Conjecture~\ref{conj-1}. As to Conjectures~\ref{conj-2} and \ref{conj-3}, Scott and Seymour \cite{SS20150} first proved that for each $l > 0$, every triangle-free graph with sufficiently large chromatic number contains holes of $l$ consecutive lengths, and thus confirmed them on triangle-free graphs. Finally, Chudnovsky, Scott and  Seymour \cite{MCSS2017} confirmed Conjecture~\ref{conj-2}, and Chudnovsky, Scott, Seymour and Spirkl \cite{MSSS2017} confirmed Conjecture~\ref{conj-3}.



We use ${\cal G}$ to denote the family of graphs that have neither triangles nor quadrilaterals,  and have no odd holes of length larger than 5.

Robertson conjectured (see \cite{NPRZ2011}) that the only 3-connected, internally 4-connected  graph in ${\cal G}$ is the Petersen graph. This conjecture is true if the requirement on internally 4-connectivity is replaced by cubic \cite{NPRZ2011}. Plummer and Zha \cite{MPXZ} presented a counterexample to Robertson's conjecture, and posed a few new questions including  (1) whether every such graph has bounded chromatic number$?$ and (2) how close to being perfect are these graphs$?$

In this note, we prove that, for every graph $G\in {\cal G}$,  $\chi(G)\le 4$ and $\chi(G)\le 3$ if $G$ has radius at most 3 (Theorem ~\ref{thm1}), which answers the first question  of Plummer and Zha, and for each vertex $u$ of $G$, the set of vertices of the same distance to $u$ induces a bipartite subgraph (Lemma~\ref{thm0}),  which answers the second question in some sense.

We introduce some notations. Let $S$ be a subset of $V(G)$, and let $x$ be a vertex of $G$. We use $G[S]$ to denote the subgraph of $G$ induced by $S$, and let $N_S(x)$ be the neighbors of $x$ in $S$. Let $x$ and $y$ be two vertices of $G$. An $xy$-path refers to a path from $x$ to $y$. We use $d_G(x, y)$ to denote the length of a shortest $xy$-path which is referred to as the distance between the two vertices. A cycle of length $k$ is simply called a $k$-cycle.

\section{Proof of the main results}

Recall that ${\cal G}$ denotes the family of graphs that have neither $C_3$ nor $C_4$, and have no odd holes of length at least 7. First, we have the following lemma on the structure of graphs in ${\cal G}$.


\begin{lemma}\label{thm0}
Let $G$ be  a graph in ${\cal G}$, let $u$ be an arbitrary vertex of $G$, and let $L_i=\{x\; : \; d_G(u, x)=i\}$ for $i=0, 1, 2, \cdots$. Then, $G[L_i]$ is bipartite for every $i$.
\end{lemma}
\begin{proof}
Since $G$ has no $C_3$, $L_0=\{u\}$, and $G[L_1]$ is an independent set. So the conclusion holds for $i=0, 1$.  Suppose that, $G[L_i]$ is bipartite for each $0\le i\le h$ for some $h\ge 1$.

Let $H=G[L_{h+1}]$, and suppose that $H$ is not bipartite. Then,  $H$ has an odd cycle and thus a 5-cycle, say $u_1u_2u_3u_4u_5u_1$. Let $v_i$ be a neighbor of $u_i$ in $L_h$. Since $G$ has neither $C_3$ nor $C_4$, $v_i\neq v_j$ if $i\neq j$.

Among all paths of length $h$ from $u$ to $v_1$ or $v_3$, we choose  $P$ to be a $uv_1$-path, and $P'$ to be a $uv_3$-path, such that $P$ and $P'$ have the most common vertices. Let $w\in L_j$ be the last common vertex of $P$ and $P'$, let $P_w=x_jx_{j+1}\ldots x_h$ be the segment of $P$ from $w$ to $v_1$, and let $P'_w=y_jy_{j+1}\ldots y_h$ be the segment of $P'$ from $w$ to $v_3$, where $x_j=y_j=w$, $x_h=v_1$ and $y_h=v_3$. Then, $j\le h-1$, and thus $C=wP_wv_1u_1u_5u_4u_3v_3P'_ww$ is an odd cycle of length $2(h-j)+5\ge 7$. Therefore, $C$ has chords.

By the choice of $P$ and $P'$, each chord of $C$ must be of the form $x_iy_i$ for some $j+2\le i\le h$. Let $i_0$ be the largest index such that $x_{i_0}y_{i_0}\in E(G)$. If $i_0<h$, then, $$u_1u_2u_3v_3y_{h-1}\ldots y_{i_0}x_{i_0}x_{i_0+1}\ldots x_{h-1}v_1u_1$$ is an odd hole of length at least 7. Therefore, $i_0=h$, i.e., $v_1v_3\in E(G)$.

With the same arguments, we can show that $\{v_2v_4, v_3v_5, v_4v_1, v_5v_2\}\subseteq E(G)$. It follows that $G[L_h]$ has a 5-cycle $v_1v_3v_5v_2v_4v_1$, a contradiction. Thus,  Lemma~\ref{thm0} holds. 
\end{proof}

\medskip

To prove our theorem, we need the following generalization of Brook's theorem by Gallai \cite{TG1963}. A graph $G$ is said to be $k$-{\em vertex}-{\em critical} if $\chi(G)=k$ and $\chi(G-v)<\chi(G)$ for each vertex $v$.

\begin{theorem}\label{Gallai}{\em (\cite{TG1963})}
Let $G$ be a $k$-vertex-critical graph, and let $V_1$ be the set of vertices of degree $k-1$ in $G$. Then every $2$-connected induced subgraph of $G[V_1]$ is either a complete graph or an odd hole.
\end{theorem}



Now, we are ready to state and prove our theorem.

\begin{theorem}\label{thm1}
Let $G$ be a graph in ${\cal G}$. Then, $\chi(G)\le 4$, and $\chi(G)\le 3$ if $G$ has radius at most $3$.
\end{theorem}

\begin{proof}
Let $u$ be an arbitrary vertex of $G$, and let $L_i=\{u : d_G(u, v)=i\}$ for an integer $i\ge 0$. By Lemma~\ref{thm0}, the vertices with even distance to $u$ induce a bipartite subgraph, and the vertices with odd distance to $u$ induce a bipartite subgraph too. Therefore, $\chi(G)\le 4$.

\medskip

Next, we suppose that $G$ has radius at most $3$. Suppose that the conclusion does not hold. Let $G$ be a counterexample in ${\cal G}$ with the smallest order, i.e.,  every proper subgraph of $G$ is $3$-colorable, and let $k=\max\{i\; :\; L_i\neq \varnothing\}$. Then,
$$k\le 3, G \mbox{ is 4-vertex-critical, and } \delta(G)\ge 3.$$

If $k=2$, then $\chi(G)\le 3$ as we may color $L_2\cup\{u\}$ with two colors by Lemma~\ref{thm0}, and color $L_1$ with the third color. So, we suppose that $k=3$.

We will show that
\begin{equation*}\label{eqa-claim}
G[L_2\cup L_3] \mbox{  is bipartite}.
\end{equation*}
Then, we may color $L_2\cup L_3\cup\{u\}$ with two colors, and color $L_1$ with the third color, and thus $\chi(G)\le 3$.

Suppose to the contrary that $G[L_2\cup L_3]$  is not bipartite. Then, $G[L_2\cup L_3]$ has odd cycles, and thus has 5-cycles. We choose $C$ to be a 5-cycle in $G[L_2\cup L_3]$ that maximizes $|V(C)\cap L_2|$. Let $C=u_1u_2u_3u_4u_5u_1$, and let $m=|V(C)\cap L_2|$.  By Lemma~\ref{thm0},
$$1\le m\le 4.$$

We may assume that $V(C)\cap L_2$ does not contain two nonadjacent vertices. For otherwise,  let $u_1, u_3\in L_2$ by symmetry. Let $P_1=uw_1u_1$ and $P_2=uw_2u_3$ be two paths. Since $G$ has neither $C_3$ nor $C_4$, $w_1\neq w_2$, $w_1w_2\not\in E(G)$, and $w_1u_1$ and $w_2u_3$ are the only two edges from $\{w_1, w_2\}$ to $\{u_1, u_3\}$. Now, $uw_1u_1u_5u_4u_3w_2u$ is an odd hole, a contradiction.

It follows that $m\le 2$,  and if $m=2$ then the two vertices in $V(C)\cap L_2$ must be adjacent.

Suppose that $m=2$, and let $u_1, u_2\in L_2$ by symmetry. Let $x$ be a neighbor of $u_4$ in $L_2$. Let $P_1=uw_1u_1$, $P_2=uw_2u_2$, and $P_3=ux'x$. It is clear that $w_1\neq w_2$, and so we suppose by symmetry that $x'\neq w_1$. Now, $uw_1u_1u_5u_4xx'u$ is an odd hole.

Finally, the only remaining case is that $m=1$, i.e.,
$$\mbox{every 5-cycle of $G[L_2\cup L_3]$ has a unique vertex in $L_2$.}$$

For convenience, we relabel the 5-cycle $C$ as $v_0u_0u_1u_2u_3v_0$, and let $v_0\in L_2$ by symmetry. Let $P=uw_0v_0$, and let $P_i=uw_iv_iu_i$ for $i\in \{0, 1, 2\}$. It is certain that
$$\mbox{$\{v_0, v_1, v_2\}$ is an independent set of size 3}$$
as $G$ has neither $C_3$ nor $C_4$.

If $N(v_1)\cap L_1\neq \{w_0\}$, we may choose $P_1$ such that $w_1\neq w_0$, then $w_0v_1, w_1v_0\not\in E(G)$ for otherwise $G[\{u, w_0, w_1, v_0, v_1\}]$ will have a $C_4$, and thus $uw_0v_0u_0u_1v_1w_1u$ is an odd hole. The same contradiction occurs if $N(v_2)\cap L_1\neq \{w_0\}$. Therefore, we have
\begin{equation}\label{eqa-u-v-v}
(N(v_0)\cup N(v_1)\cup N(v_2))\cap L_1=\{w_0\}.
\end{equation}

Recall that for a subset $S$ of vertices and a vertex $z$, $N_S(z)$ denotes the neighbors of $z$ in $S$.

Let $B$ be the component of $G[L_3]$ that contains $u_0$. We will show that
\begin{equation}\label{eqa-cycle}
\mbox{$B$ is a cycle that can be labelled as $u_0u_1\ldots u_{3q-1}$ for some integer $q$}.
\end{equation}
and for each integer $i$ and each integer $j\in\{0, 1, 2\}$,
\begin{equation}\label{eqa-l2}
d(u_i)=3, \mbox{ and } N_{L_2}(u_i)=\{v_j\}\;\mbox{ if } i\equiv j \mbox{ mod } 3.
\end{equation}



We proceed to prove (\ref{eqa-cycle}) and (\ref{eqa-l2}), and prove (\ref{eqa-l2}) by induction first.

If $N_{L_2}(u_3)\neq \{v_0\}$, we may choose $P_3=uw_3v_3u_3$ such that $v_3\neq v_0$, then $v_2\neq v_3$, $w_3\neq w_0$, and $\{v_2w_3, w_0v_3, v_2v_3, w_0w_3\}\cap E(G)=\varnothing$ by (\ref{eqa-u-v-v}) (as $G$ has neither $C_3$ nor $C_4$). Now, $uw_3v_3u_3u_2v_2w_0u$ is an odd hole (note that $w_2=w_0$ by (\ref{eqa-u-v-v})), a contradiction.  The same happens if $N_{L_2}(u_0)\neq \{v_0\}$. So,
\begin{equation}\label{eqa-associate0}
N_{L_2}(u_0)\cup N_{L_2}(u_3)=\{v_0\}.
\end{equation}


Since $\delta(G)\ge 3$ and $k=3$, both $|N_B(u_0)|>1$ and $|N_B(u_3)|>1$. Choose $u_4\in N_B(u_3)\setminus \{u_2\}$, and let $P_4=uw_4v_4u_4$. If $N_{L_1}(v_{4})\neq \{w_0\}$, we may choose $P_{4}$ such that $w_{4}\neq w_0$, then it is easy to check that $uw_0v_0u_3u_{4}v_{4}w_{4}u$ would be an odd hole. So,
$$N_{L_1}(v_4)=\{w_0\}.$$

If $N_{L_2}(u_{4})\neq \{v_1\}$, we may choose $P_{4}$ such that $v_{4}\neq v_1$, then $w_0v_{4}u_{4}u_3u_2u_1v_1w_0$ would be  an odd hole, a contradiction. So, we  may suppose, by symmetry, that
\begin{equation}\label{eqa-u2}
N_{L_2}(x)=\{v_1\} \mbox{ for every vertex } x\in N_B(u_3)\setminus\{u_2\},
\end{equation}
and
\begin{equation}\label{eqa-u0}
N_{L_2}(y)=\{v_2\} \mbox{ for every vertex } y\in N_B(u_0)\setminus\{u_1\}.
\end{equation}


Let $u_{-1}$ be a vertex in $N_B(u_0)\setminus\{u_1\}$. If $N_{B}(u_0)\neq\{u_{-1}, u_1\}$, choose $z_0\in N_{B}(u_0)\setminus\{u_{-1}, u_1\}$, then $z_0v_2\in E(G)$ by (\ref{eqa-u0}) and thus $z_0v_2u_{-1}u_0z_0$ would be a $C_4$. Therefore, we may suppose, by (\ref{eqa-associate0}) and by symmetry, that
%\begin{equation}\label{eqa-u2u5}
$$N(u_0)=\{u_{-1}, u_1, v_0\}\; \mbox{ and } N(u_3)=\{u_2, u_4, v_0\}.$$
%\end{equation}


By applying the same arguments as that used on  $C$ to 5-cycles $v_1u_1u_2u_3u_4v_1$ and $v_2u_{-1}u_0u_1u_2v_2$, we see that
%\begin{equation}\label{eqa-u3u4}
$$N(u_1)=\{u_0, u_2, v_1\} \mbox{ and } N(u_2)=\{u_1, u_3, v_2\}.$$
%\end{equation}


We have proved (\ref{eqa-l2}) for $i\in \{0, 1, 2, 3\}$. Suppose that (\ref{eqa-l2}) holds for $i\in \{0, 1, \ldots, m\}$, where $m\ge 3$. Let $i=m+1$, and suppose, without loss of generality, that $m\equiv 1$ (mod 3). Then, $v_1u_{m-3}u_{m-2}u_{m-1}u_mv_1$ is a 5-cycle, $N_{L_2}(u_{m-2})=\{v_2\}$, and $N_{L_2}(u_{m-1})=\{v_0\}$ by the inductive hypothesis.  By applying the same argument to $v_1u_{m-3}u_{m-2}u_{m-1}u_mv_1$ as that used on $C$, we see that
$$N_{L_2}(u_{m+1})=\{v_2\} \; \mbox{ and } \; d(u_{m+1})=3.$$
Therefore, (\ref{eqa-l2}) holds for all $i$.


Since $G$ is finite, there must be an integer $j$ such that $u_0u_j\in E(G)$. Suppose that $j\equiv r$ (mod 3). By (\ref{eqa-l2}), $v_0u_0u_jv_0$ would be a $C_3$ if $r=0$, and $u_0u_1v_1u_ju_0$ would be  a $C_4$ if $r=1$. Therefore, $r=2$, and so $B$ is a cycle of length $j+1$ which is a multiple of $3$. This completes the proof of (\ref{eqa-cycle}).

Let $H$ be the subgraph of $G$ induced by the vertices of degree 3. Now, $B$ is a 2-connected subgraph of $H$, which is neither complete nor an odd hole. This contradiction to Theorem~\ref{Gallai} shows that $G[L_2\cup L_3]$  is bipartite. Now, by coloring $L_2\cup L_3\cup\{u\}$ with two colors and coloring $L_1$ with the third color, we can complete the proof of Theorem~\ref{thm1}. 
\end{proof}

\medskip

Finally, we would like to mention that in \cite{MPXZ}, Plummer and Zha also conjectured that the graphs in ${\cal G}$ may have chromatic number at most 3. This problem is still open in general.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}
We thank the referees sincerely for their helpful suggestions. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain}
% \bibliography{myBibFile}
% If you use BibTeX to create a bibliography
% then copy and past the contents of your .bbl file into your .tex file


\begin{thebibliography}{99}

\bibitem{beineke1} L.~W. Beineke. \newblock Derived graphs and digraphs. \newblock In: {\em H. Sachs, Beitr\"{a}ge zur Graphentheorie},  page 17--33. Teubner Leibzig, 1968.

\bibitem{CRST2006}  M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas. \newblock The strong
perfect graph theorem. \newblock{\em Annals of Mathematics},  164:51--229, 2006.


\bibitem{MRST2010} M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas. \newblock $K_4$-free graphs with no odd holes. \newblock{\em J. Combinatorial Theory Ser. B}, 100:313--331, 2010.

\bibitem{CPST2013} M. Chudnovsky, I. Penev, A. Scott and N. Trotignon. \newblock Substitution and $\chi$-boundedness. \newblock {\em J. Combinatorial Theory Ser. B}, 103:567--586, 2013.

\bibitem{MCSS2017} M. Chudnovsky, A.~D. Scott and  P. Seymour. \newblock Induced subgraphs of graphs with large chromatic number. III. long holes. \newblock to appear in {\em Combinatorica}.


\bibitem{MSSS2017} M. Chudnovsky, A.~D. Scott, P. Seymour and S. Spirkl. \newblock Induced subgraphs of graphs with large chromatic number. VIII. long odd holes. \newblock manuscript.


\bibitem{BD1947} B. Descartes. \newblock A three colour problem. \newblock {\em Eureka} 21, 1947.

\bibitem{PE1959} P. Erd\H{o}s. \newblock Graph theory and probability. \newblock {\em Canad. J. Math}, 11:34--38, 1959.

\bibitem{TG1963} T. Gallai. \newblock Kritische graphen. \newblock{\em I. Publ. Math. Inst. Hungar. Acad. Sci.}, 8:165--102, 1963.

\bibitem{gyarfas1} A. Gy\'{a}rf\'{a}s. \newblock On Ramsey covering-numbers. \newblock {\em Colloquia Mathematic Societatis J\'{a}nos Bolyai 10, Infinite and Finite Sets.}, pp. 801--816,  North-Holland/American Elsevier, New York, 1975.

\bibitem{gyarfas2} A. Gy\'{a}rf\'{a}s, E. Szemer$\acute{e}$di and Tuza. \newblock Induced subtrees in graphs of large chromatic number. \newblock {\em Discrete Math.}, 30:235--244, 1980.

\bibitem{gyarfas1987} A. Gy\'{a}rf\'{a}s. \newblock Problems from the world surrounding perfect graphs. \newblock {\em Zastosow. Mat.}, 19:413--441.


\bibitem{kierstead1} H.~A. Kierstead and S.~G. Penrice. \newblock Radius two trees specify $\chi(G)$-bounded classes. \newblock{\em J. Graph Theory}, 18:110--120, 1994.

\bibitem{KZ2004} H.~A. Kierstead and Y. Zhu. \newblock Radius three trees in graphs with
large chromatic number. \newblock {\em SIAM J. Disc. Math.},  17:571--581, 2004.

\bibitem{JM1955} J. Mycielski. \newblock Sur le coloriage des graphes. \newblock {\em Colloq. Math.}, 3:161--162, 1955.

\bibitem{NPRZ2011} D. Nelson, M. Plummer, N. Robertson and X. Zha. \newblock On a conjecture concerning the Petersen graph. \newblock {\em The Electronic J. of Combin.}, 18:\#P20,  2011.

\bibitem{MPXZ} M. Plummer and X. Zha. \newblock On a conjecture concerning the Petersen Graph:
Part II. \newblock {\em The Electronic J. of Combin.}, 21:\#P1.34, 2014.


\bibitem{scott1} A.~D. Scott. \newblock Induced trees in graphs of large chromatic number. \newblock {\em J. Graph Theory}, 24:297--311, 1997.

\bibitem{scott1999} A.~D. Scott. \newblock Induced cycles and chromatic number. \newblock {\em J. Combinatorial Theory Ser. B}, 76:150--154, 1999.

\bibitem{SS2015} A.~D. Scott and P. Seymour. \newblock Induced subgraphs of graphs with large chromatic number. I. odd holes. \newblock {\em J. Combinatorial Theory Ser. B}, 12168--84, 2016.


\bibitem{SS20150} A.~D. Scott and P. Seymour. \newblock Induced subgraphs of graphs with large chromatic number. IV. consecutive holes. \newblock
\url{https://web.math.princeton.edu/~pds/papers/holeseq/paper.pdf}

\bibitem{sumner1} D.~P. Sumner. \newblock Subtrees of a graph and chromatic number, \newblock In {\em The Theory and Applications of Graphs}, pp. 557--576, John Wiley \& Sons, New York, 1981.

\bibitem{AAZ1949} A.~A. Zykov. \newblock On some properties of linear complexes (in Russian). \newblock {\em Mat. Sbornik}, 24:313--319, 1949.

\bibitem{vizing1} V.~G. Vizing. \newblock The chromatic class of a multigraph. \newblock {\em Kibernetika(kiev)}, 329--39, 1965.


\end{thebibliography}

\end{document}