\documentclass[12pt]{article}
\usepackage{amssymb,latexsym}
\usepackage{amsmath}
%\usepackage[dvipdfm]{graphicx}
\usepackage{tikz}
\usepackage{verbatim}
\usepackage{e-jc}
\usetikzlibrary {positioning}
  \usetikzlibrary{arrows,topaths}
%%%%%%%%%%%%%%%%
\textheight 8in\textwidth 6in\oddsidemargin 0in\evensidemargin 0in
\newtheorem{theorem}{Theorem}
\newenvironment{proof}{{\em Proof.}}{\hfill $\Box$ \vskip 0.5cm}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{observation}{Observation}
\newtheorem{problem}{Problem}
\newtheorem{proposition}{Proposition}
\newtheorem{remark}{Remark}
\newtheorem{claim}{Claim}
\newtheorem{fact}{Fact}\newtheorem{conjecture}{Conjecture}
\newtheorem{definition}{Definition}
\newtheorem{example}{Example}
\def\bs{\bigskip}\def\ms{\medskip}\def\ds{\displaystyle}
\def\beq{\begin{equation}}\def\eeq{\end{equation}}
\def\beqn{\begin{eqnarray}}\def\eeqn{\end{eqnarray}}
\def\pont{\hspace{-6pt}{\bf.\ }}
\def\eps{\varepsilon}\def\ffi{\varphi}
\def\qed{\ifhmode\unskip\nobreak\fi\quad\ifmmode\Box\else$\Box$\fi}

\def\marrow{{\boldmath {\marginpar[\hfill$\Rrightarrow \Rrightarrow$]{$\Lleftarrow \Lleftarrow$}}}}
\def\janos#1{{\sc J\'anos: }{\marrow\sf #1}}

\title{Induced colorful trees and paths in large chromatic graphs}
\author{Andr\'as Gy\'arf\'as \thanks{Research supported in part by
grant  (no.\   K104343) from the National Development Agency of
    Hungary, based on a source from the Research and Technology Innovation
    Fund.}\\[-0.8ex]
\small Alfr\'ed R\'enyi Institute of Mathematics\\[-0.8ex]
\small Hungarian Academy of Sciences\\[-0.8ex]
\small Budapest, P.O. Box 127\\[-0.8ex]
\small Budapest, Hungary, H-1364\\
\and
G\'{a}bor N. S\'ark\"ozy\thanks{Research supported in part by
grant  (no.\   K104343) from the National Development Agency of
    Hungary, based on a source from the Research and Technology Innovation
    Fund.}\\[-0.8ex]
\small Alfr\'ed R\'enyi Institute of Mathematics\\[-0.8ex]
\small Hungarian Academy of Sciences\\[-0.8ex]
\small Budapest, P.O. Box 127\\[-0.8ex]
\small Budapest, Hungary, H-1364\\
and\\
\small Computer Science Department\\[-0.8ex]
\small Worcester Polytechnic Institute\\[-0.8ex]
\small Worcester, MA, USA 01609\\[-0.8ex]
\small \texttt{gsarkozy@cs.wpi.edu}\\[-0.8ex]}

\begin{document}
\maketitle


\begin{abstract} In a proper vertex coloring of a graph a subgraph is {\em colorful} if its vertices are colored with different colors. It is well-known (see for example in \cite{gyszt}) that in every proper coloring of a $k$-chromatic graph there is a colorful path $P_k$ on $k$ vertices. The first author proved (\cite{gy}) that $k$-chromatic and {\em triangle-free} graphs have a path $P_k$ which is an {\em induced} subgraph. N.R. Aravind conjectured that these results can be put together: in every proper coloring of a $k$-chromatic triangle-free graph, there is an induced colorful $P_k$. Here we prove the following weaker result providing some evidence towards this conjecture.

For a suitable function $f(k)$, in any proper coloring of an $f(k)$-chromatic graph of girth at least five, there is an induced colorful path on $k$ vertices.
\end{abstract}

\section{Introduction}
A special case of a result of the first author in \cite{gy} says that every triangle-free $k$-chromatic graph $G$ contains an induced path on $k$ vertices. The following more general conjecture is attributed to N.R. Aravind in \cite{bbcf}. A path (or more generally a subgraph) in a proper coloring of $G$ is called {\em colorful} if its vertices are colored with distinct colors.

\begin{conjecture}\pont \label{ara} In any proper coloring of any triangle free $k$-chromatic graph $G$ there is an induced colorful path on $k$ vertices.
\end{conjecture}

The main result of \cite{bbcf} is the proof of Conjecture \ref{ara} for the case when $G$ has girth $k$.
One can easily see that Conjecture \ref{ara} cannot be extended from paths to other trees. Indeed, the following example shows that there are graphs of arbitrary large chromatic number with proper colorings that contain no colorful $K_{1,3}$. For other similar problems on colorful paths see \cite{bb}.

\begin{example}\pont \label{ex} (\cite{efhkrs,kt}) Let $SH_n$ be the graph whose vertex set is the set of $n\choose 3$ triples of $[n]$ and where for $1\le i<j<k<\ell\le n$, vertex $(i,j,k)$ is adjacent to $(j,k,\ell)$. Coloring $(i,j,k)$ with $j$, we have a proper coloring containing no colorful  $K_{1,3}$ and the chromatic number of $SH_n$ is unbounded.
\end{example}

 However, if we drop the colorful condition then (according to a well-known conjecture of the first author and Sumner \cite{gyconj,sumner}) the existence of any induced subtree might be guaranteed in triangle-free graphs of sufficiently large chromatic number. If the triangle-free condition is strengthened, considering the family ${\cal{G}}_5$ of graphs with no cycles of length three and four, then the induced tree conjecture becomes easy, in fact large minimum degree can replace the chromatic bound.

\begin{theorem}\pont \label{c3c4} (Gy\'arf\'as, Szemer\'edi, Tuza \cite{gyszt}). Let $T_k$ be a tree on $k$ vertices. Then every graph in ${\cal{G}}_5$ with minimum degree at least $k-1$ contains $T_k$ as an induced subgraph.
\end{theorem}

Assume we have a proper coloring on $G$. The color degree $cod_G(v)$ is the number of distinct colors appearing on the neighbors of $v$ and $cod(G)=\min \{cod_G(v): v\in V(G) \}$. Our first result is the following ``colorful'' variant of Theorem \ref{c3c4}.

\begin{theorem}\pont \label{c3c4cod} Let $T_k$ be a tree on $k\ge 4$ vertices. Then every proper coloring of $G\in {\cal{G}}_5$ with $cod(G)\ge 2k-5$ contains $T_k$ as an induced colorful subgraph.
\end{theorem}




A related subject is to find induced subgraphs in {\em oriented} large chromatic triangle-free graphs, for old and new results see \cite{abbchmz}.  By a result of Chv\'atal \cite{ch}, acyclic digraphs with no induced subgraph with edges $(1,2),(2,3),(4,3)$ are perfect. On the other hand, triangle-free digraphs with no induced subgraph with edges $(1,2),(3,2),(3,4)$ exist with an arbitrary large chromatic number (see \cite{gypr}). In \cite{gypr} it was asked what happens for the directed $P_4=(1,2),(2,3),(3,4)$? This was answered by Kierstead and Trotter \cite{kt} by constructing arbitrary large chromatic triangle-free oriented graphs without induced directed $P_4$. They also proved that if the clique size of a graph is fixed and its chromatic number is large then in every proper coloring and with orienting edges from smaller to larger color, there is {\em either} an  induced colorful star $S_k$ (a vertex with outdegree $k$) {\em or} an induced colorful directed path $P_k$. Here we present a result in a similar vein.

\begin{theorem}\pont \label{treepath}  Let $k$ be a positive integer and $T_k$ be a tree on $k$ vertices. There exists a function $f(k)$ such that the following holds. If $G\in {\cal{G}}_5$ with $\chi(G)\ge f(k)$ then in any proper coloring of $G$ and in any acyclic orientation of $G$ there is either an induced colorful $T_k$ or an induced directed path $P_k$.
\end{theorem}

Note that in Theorem \ref{treepath} the orientation of $T_k$ is not prescribed (but $P_k$ is the directed path). Also, $P_k$ is induced but not necessarily colorful. However, if $G$ is oriented so that for $c(v)<c(w)$ we have $(v,w)\in E(G)$, $P_k$ must be  colorful as well. Selecting this acyclic orientation and $T_k=P_k$, we get from Theorem \ref{treepath} the following weakened form of Conjecture \ref{ara}.

\begin{corollary}\pont \label{cor}In any proper coloring of an $f(k)$-chromatic graph $G\in {\cal{G}}_5$, $G$ contains an induced colorful path on $k$ vertices.
\end{corollary}

To get closer to Conjecture \ref{ara} it would be very desirable to forbid only triangles (and allow four-cycles) in Corollary \ref{cor}.
It is worth considering the following problem.

\begin{problem}\pont \label{diff} Let $k$ be a positive integer and $T_k$ be a tree on $k$ vertices. Is there a function $f(k)$ such that the following holds? If $G$ is a triangle-free graph with $\chi(G)\ge f(k)$ then in any proper coloring of $G$ with $\chi(G)$ colors, there is an induced colorful $T_k$.
\end{problem}

Problem \ref{diff} seems certainly difficult since it contains the Gy\'arf\'as - Sumner conjecture. The case when $T_k$ is a path should be easier, it is weaker than Conjecture \ref{ara}. Note that the condition that the proper coloring of $G$ must use $\chi(G)$ colors, eliminates Example \ref{ex}. In fact, Problem \ref{diff} has an affirmative answer for any $k$-vertex star with $f(k)=k$, since a $k$-chromatic graph must contain a vertex adjacent to all other color classes in any $k$-coloring and these neighbors form an independent set since $G$ is triangle-free.





\section{Proofs}
\noindent{\bf Proof of Theorem \ref{c3c4cod}.} We construct an induced colorful $T_k$ by induction. For $k=4$ we have two trees to construct from the condition that $cod(G)\ge 3$. For each of the two trees the proof is obvious and we omit the details.

For the inductive step, assume $v$ is a leaf of a tree $T_k$ with neighbor $w$ in $T_k$. Let $T^*$ be the tree $T_k-v$. By induction we find $T^*$ as an induced colorful subgraph of $G$ so $w\in V(T^*)\subseteq V(G)$.  By the condition on the color degree, $w$ is adjacent to a set $S\subset V(G)\setminus V(T^*)$ such that $|S|\ge k-3$, $S$ is colorful and  $\{c(v): v\in S\}\cap \{c(v): v\in T^*\}=\emptyset$. No edge of $G$ goes from $S$ to any vertex of $T^*-\{w\}$ that is at distance one or two from $w$ in $T^*$ since $G \in {\cal{G}}_5$. There are at most $k-4$ vertices of $T^*$ that are at distance at least three from $w$ in $T^*$ and each of them sends at most one edge to $S$ since $G$ is $C_4$-free. Thus at least one vertex in $S$ is nonadjacent to any vertex of $T^*-\{w\}$ and it extends $T^*$ to a tree isomorphic to $T_k$ and it is an induced colorful subgraph of $G$. \qed

\bigskip
\bigskip


\noindent{\bf Proof of Theorem \ref{treepath}.} Let $c$ be a proper coloring of $G$,  $G^*$ is an orientation of $G$.  Assume that we have an ordering $<$ on $V(G)$, then the forward color degree $fcod_G(v)$ is the number of distinct colors appearing on the neighbors of $v$ that are larger than $v$, i.e. $$fcod_G(v)=|\{c(w): vw\in E(G), v<w \}|.$$
We shall prove that the following function $f(k)$ is suitable.

$$f(k)=\left\{\begin{array} {l}
k \text{\quad if $1\leq k \leq 4$ }\\
\\
g^2(k) \text{\quad if  $k\ge 5$, }\\
\end{array} \right.
$$

where

$$g(k)=\left\{\begin{array} {l}
k \text{\quad if $1\le k\le 4$}\\
\\
(2k-6)g(k-1)+1 \text{\quad if  $k\ge 5$. }\\
\end{array} \right.
$$

For $k\le 3$ the theorem holds with the first alternative: a $1$-chromatic graph has a vertex, a $2$-chromatic graph has an edge, $3$-chromatic graphs without triangles have odd induced cycles of length at least 5 which must contain colorful induced $P_3$. Thus we assume $k\ge 4$.

Assume first that  $G$ has a subgraph $G'$ such that $cod_{G'}(v)\ge 2k-5$ for every $v\in G'$. By Theorem \ref{c3c4cod} we find a colorful induced $T_k=P_k$ in $G'$.

Now we may assume that $G$ has no subgraph $G'$ such that $cod_{G'}(v)\ge 2k-5=d$ for every $v\in G'$. Thus we can define an ordering $\pi$ on $V(G)$ by repeatedly selecting vertices $v_1,\dots, v_i, \ldots$  such that $fcod_{G_i}(v_i) < d$ for all $v_i\in V(G)$, where $G_i$ is the subgraph of $G$ induced by the vertices $(V(G)\setminus \{v_1, \ldots, v_{i-1}\})$.


The oriented graph $G^*$ can be written as $G_1\cup G_2$ where both graphs have vertex set $V(G)$ and $G_1$ contains the edges of $G^*$ oriented forward with respect to $\pi$ and $G_2$ contains the edges of $G^*$ oriented backward with respect to $\pi$.
By the Gallai - Vitaver - Roy theorem (\cite{lo}, Ex. 9.9) we can find a directed path $P_t$ in one of the two $G_i$-s with $t=g(k)$. Indeed, for $k=4$, $g(4)=f(4)=4$ thus $G$ is $4$-chromatic, it contains $P_4$ which is induced since $G\in {\cal{G}}_5$. For $k>4$, we use that $f(k)\le \chi(G^*)=\chi(G_1\cup G_2)\le \chi(G_1)\chi(G_2)$,  thus $\chi(G_i)\ge t=\sqrt{f(k)}=g(k)$ for some $i\in \{1,2\}$. Assume that $P_t$ is oriented forward in the ordering $\pi$.




\begin{lemma}\pont \label{forpath}$P=P_t$ contains an induced $P_k$ starting from the first vertex of $P$.
\end{lemma}

\noindent{\bf Proof. }
For $k=4$ the lemma is obvious since in a graph $G\in {\cal{G}}_5$ any $P_4$ is induced. Assuming that it is true for some $k-1\ge 4$, consider the at most $d-1=2k-6$ forward edges from the starting point $v\in P$ to other points $w_1,\dots,w_s$ of $P$ where $s\le 2k-6$. This partitions $P-v$ into at most $2k-6$ disjoint paths, $Q_1=w_1\dots,Q_2=w_2\dots,Q_s=w_s\dots$, one of them, $Q_j$, must contain at least ${g(k)-1\over 2k-6}=g(k-1)$ vertices. By induction, $Q_j$ contains an induced $P_{k-1}$ from its first vertex $w_j$. No edge of $G$ is oriented from $Q_j$ to $v$ since the orientation is acyclic. Also, apart from $vw_j$, no edge of $G$ is oriented from $v$ to $Q_j$ by the definition of $Q_j$. Thus $vP_{k-1}$ is the required induced $P_k$. This proves the lemma. \qed


The proof of Theorem \ref{treepath} is now finished, observing that if $P_t$ is oriented backward in the ordering $\pi$, Lemma \ref{forpath} should be used in ``backward'' version, stating that $P=P_t$ contains an induced $P_k$ ending in the first vertex of $P$.  \qed



\begin{thebibliography}{99}

\bibitem{abbchmz} P. Aboulker, J. Bang-Jensen, N. Bousquet, P. Charbit, F. Havet, F. Maffray,\\ J. Zemora, $\chi$-bounded families of oriented graphs, {\em arXiv:1605.07411v1}.

\bibitem{bbcf} J. Babu, M. Basavaraju, L. S. Chandran, M. C. Francis, On induced colorful paths in triangle-free graphs, {\em arXiv:1604.06070v1}.

\bibitem{bb} S. Bessy, N. Bousquet, Colorful paths for $3$-chromatic graphs, {\em arXiv:1503.00965}.

\bibitem{ch} V. Chv\'atal, Perfectly ordered graphs, {\em in: Topics on Perfect Graphs, Ann. Discrete Math.} {\bf 21} (1984) 63-65.

\bibitem{efhkrs} P. Erd\H os, Z. F\"uredi, A. Hajnal, P. Komj\'ath, V. R\"odl, \'A. Seress, Coloring graphs with locally few colors, {\em Discrete Math.} {\bf 39} (1986) 21-34.


\bibitem{gyconj} A. Gy\'arf\'as, On Ramsey covering numbers, {\em Infinite and Finite Sets, Coll. Math. Soc. J\'anos Bolyai} {\bf 10} (1973) 801-816.

\bibitem{gy} A. Gy\'arf\'as, Problems from the world surounding perfect graphs, {Zastowania Matematyki Applicationes Mathematicae} {\bf XIX, 3-4} (1987) 413-444.

\bibitem{gyszt} A. Gy\'arf\'as, E. Szemer\'edi, Zs. Tuza, Induced subtrees in graphs of large chromatic number, {\em Discrete Math.} {\bf 30} (1980) 235-244.

\bibitem{gypr} A. Gy\'arf\'as, Problem 115, {\em Discrete Math.} {\bf 79} (1989-90) 109-110.


\bibitem{kt} H.A. Kierstead, W.T. Trotter, Colorful induced subgraphs, {\em Discrete Math.} {\bf 101} (1992) 165-169.

\bibitem{lo} L. Lov\'asz, Combinatorial Problems and Exercises, {\em North Holland}, 1993.

\bibitem{sumner} D. P. Sumner, Subtrees of a graph and chromatic number, {\em in: G. Chartrand, ed., The Theory and Applications of Graphs} (Wiley, New York, 1981) 557-576.

\end{thebibliography}

\end{document}


 Set $t=d(k-1)+1$. We define a coloring $C$ on $V(G)$ such that the colors will be vectors $(C_1(v),\dots, C_t(v)$ where each $C_i(v)$ is a pair of nonnegative integers whose sum is at most $d$. The number of such pairs (order is important) is ${d+2\choose 2}$. Thus $C$ uses ${d+2\choose 2}^t$ colors. To define $C$ recursively, let $C_0(v)=(0,0)$ for all $v\in V$. Suppose that $C_j(v)$ is already defined for all $j\le i$ and for all $v\in V$. Set $$V(v,i)=\{w\in V: C_j(v)=C_j(w) \mbox{ for all } v\in V\},$$ then set $C_{i+1}(v)=(p,q)$ where $$fcod_{G[V(v,i)]}(v)=p+q, fcod^+_{G[V(v,i)]}(v)=p, fcod^-_{G[V(v,i)]}(v)=q.$$


Let $P=(v_1,\dots,v_t)$ be the longest colorful induced path in $G'$, w.l.o.g. $c(v_i)=i$. Let $S$ be the set of neighbors of $v_1$ not on $P$ (all neighbors of $v_1$ except $v_2$). The vertices of $S$ use at most $t-1$ colors present on $P$ and at most $t-2$ colors not present on $P$. The first statement is obvious, the second follows from the fact that the vertices $v_3,\dots,v_t$ can send at most one edge to $S$ otherwise we could have a $C_4$ in $G'$. Thus $cod(v_1)\le 2t-3$ which contradicts the assumption unless $t\ge k$, giving the first alternative of the theorem.

We shall write $fcod_G(v)=fcod^+_G(v)+fcod^-_G(v)$ where
$$|fcod^+_G(v)=\{c(w): vw\in E(G^*), v<w \}|,|fcod^-_G(v)=\{c(w): wv\in E(G^*), v<w \}|.$$