% EJC papers must begin as follows
\documentclass[12pt]{article}
\usepackage{e-jc}

% only use standard LaTeX packages
% only include essential packages

% 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
% use \sloppy to avoid overly wide text
\sloppy

% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{thm}{Theorem}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{fact}[thm]{Fact}
\newtheorem{observation}[thm]{Observation}
\newtheorem{clm}[thm]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[thm]{Definition}
\newtheorem{example}[thm]{Example}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{open}[thm]{Open Problem}
\newtheorem{prob}[thm]{Problem}
\newtheorem{question}[thm]{Question}

\theoremstyle{remark}
\newtheorem{rem}[thm]{Remark}
\newtheorem{note}[thm]{Note}

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

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

\title{\bf Partition of Graphs and Hypergraphs into Monochromatic Connected Parts}

% 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{Shinya Fujita\thanks{Corresponding author; Supported by the Japan Society for the Promotion of Science Grant-in-Aid for Young Scientists (B)
(20740068).}\\
\small Department of Integrated Design Engineering\\[-0.8ex]
\small Maebashi Institute of Technology\\[-0.8ex] 
\small 460-1 Kamisadori, Maebashi 371-0816, Japan \\
\small\tt shinya.fujita.ph.d@gmail.com\\
\and
Michitaka Furuya\\
\small Department of Mathematical Information Science\\[-0.8ex]
\small Tokyo University of Science\\[-0.8ex]
\small 1-3 Kagurazaka, Shinjuku-ku, Tokyo 162-8601, Japan\\
\small\tt michitaka.furuya@gmail.com\\
\and 
Andr\'{a}s Gy\'{a}rf\'{a}s\\
\small Alfr\'{e}d R\'{e}nyi Institute of Mathematics\\[-0.8ex]
\small Hungarian Academy of Sciences\\[-0.8ex]
\small 1364 Budapest P.O.Box 127, Hungary\\
\small\tt andras.gyarfas@renyi.mta.hu\\
\and
\'{A}gnes T\'{o}th\thanks{Partially supported by the grant T\'AMOP-4.2.1/B-09/1/KMR-2010-0002.}\\
\small Department of Computer Science and Information Theory\\[-0.8ex]
\small Budapest University of Technology and Economics\\[-0.8ex]
\small 1521 Budapest, P.O. Box 91, Hungary\\
\small\tt tothagi@cs.bme.hu
}

% \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{XXX, 2012}{XXX, 2012}\\
\small Mathematics Subject Classifications: 05C15, 05C70}




%\documentclass[11pt,a4paper]{article}

%\usepackage{amsmath,amsthm,amssymb}
%\usepackage{fullpage}
%if you do not have the package fullpage contained in the preprint package bundle,
%then use the following line instead of the previous one, and copy the fullpage2.sty file into the folder of your tex source 
%\usepackage{fullpage2}
%\newtheorem{thm}{Theorem}
%\newtheorem{prop}[thm]{Proposition}
%\newtheorem{cor}[thm]{Corollary}
%\newtheorem{lem}[thm]{Lemma}
%\newtheorem*{clm}{Claim}
%\newtheorem{conj}{Conjecture}
%\newtheorem{prob}[conj]{Problem}
%\theoremstyle{remark}
%\newtheorem*{rem}{Remark}

%\linespread{1.3}

%\usepackage{refcheck}

\begin{document}
%\title{Partition of graphs and hypergraphs into monochromatic connected parts}
%\author{Shinya Fujita\thanks{Corresponding author; Department of Integrated Design Engineering, Maebashi Institute of Technology, 460-1 Kamisadori, Maebashi 371-0816, Japan, Email: shinya.fujita.ph.d@gmail.com; Supported by the Japan Society for the Promotion of Science Grant-in-Aid for Young Scientists (B)
%(20740068).
%}, Michitaka Furuya\thanks{Department of Mathematical Information Science, Tokyo University of Science, 1-3 Kagurazaka, Shinjuku-ku, Tokyo 162-8601, Japan, Email: michitaka.furuya@gmail.com},
%Andr\'{a}s Gy\'{a}rf\'{a}s,\thanks{Computer and Automation Research Institute, Hungarian Academy of Sciences, 1518 Budapest, P.O. Box 63, Hungary, Email: gyarfas@sztaki.hu}
%\'{A}gnes T\'{o}th\thanks{Department of Computer Science and Information Theory, Budapest University of Technology and Economics, 1521 Budapest, P.O. Box 91, Hungary, Email: tothagi@cs.bme.hu; The results discussed in the paper are partially supported by the grant T\'AMOP-4.2.1/B-09/1/KMR-2010-0002.}\\
%}

%\date{}
\maketitle
%\thispagestyle{empty}

\begin{abstract}
We show that two results on \textit{covering} of edge colored graphs by monochromatic connected parts can be extended to \textit{partitioning}. We prove that for any $2$-edge-colored non-trivial $r$-uniform hypergraph $H$, the vertex set can be partitioned into at most $\alpha (H)-r+2$ monochromatic connected parts, where $\alpha (H)$ is the maximum size of a set of vertices that does not contain any edge. In particular, any $2$-edge-colored graph $G$ can be partitioned into $\alpha(G)$ monochromatic connected parts, where $\alpha (G)$ denotes the independence number of $G$. This extends K\"onig's theorem, a special case of Ryser's conjecture.

Our second result is about Gallai-colorings, i.e. edge-colorings of graphs without $3$-edge-colored triangles. We show that for any Gallai-coloring of a graph $G$, the vertex set of $G$ can be partitioned into monochromatic connected parts, where the number of parts depends only on $\alpha(G)$. This extends its cover-version proved earlier by Simonyi and two of the authors.
\end{abstract}


\section{Introduction}

In this paper we prove two results about partitioning edge-colored graphs (and hypergraphs) into monochromatic connected parts. Let $k$ be a positive integer. A $k$-edge-colored (hyper)graph is a (hyper)graph whose edges are colored with $k$ colors. It was observed in \cite{G} that a well-known conjecture of Ryser which was stated in the thesis of his student Henderson \cite{HE} can be formulated as follows.

\begin{conj}\label{rysvar}
If the edges of a graph are colored with $k$ colors then $V(G)$ can be covered by the vertices of at most $\alpha(G)(k-1)$ monochromatic connected components (trees).
\end{conj}

Ryser's conjecture (thus Conjecture~\ref{rysvar}) is known to be true for $k=2$ (when it is equivalent to K\"onig's theorem). After partial results \cite{H}, \cite{SZT}, the case $k=3$ was solved by Aharoni \cite{A}, relying on an interesting topological method established in \cite{AH}. Recently Kir\'aly \cite{K} showed, somewhat surprisingly, that an analogue of Conjecture~\ref{rysvar} holds for hypergraphs: for $r\ge 3$, in every $k$-coloring of the edges of a complete $r$-uniform hypergraph, the vertex set can be covered by at most $\lfloor\frac{k}{r}\rfloor$ monochromatic connected components (and this is best possible). The authors in \cite{FFGT} will consider extensions of Kir\'aly's result for non-complete hypergraphs.

The strengthening of Conjecture~\ref{rysvar} from covering to partition was suggested in \cite{EGP} (and proved for $k=3,\alpha(G)=1$). In this paper we extend the $k=2$ case of Conjecture~\ref{rysvar} for hypergraphs and for partitions instead of covers (Theorem~\ref{partition}).

Our second partition result (Theorem~\ref{mainthm}) is about {\em Gallai-colorings} of graphs where the number of colors is not restricted but $3$-edge-colored triangles are forbidden. This extends the main result of \cite{GST} from cover to partition.

\bigskip

We consider hypergraphs $H$ with edges of size at least two, i.e. we do not allow singleton edges. Let $V(H)$, $E(H)$ denote the set of vertices and the set of edges of $H$, respectively. A hypergraph is $r$-uniform if all edges have $r\ge 2$ vertices (graphs are $2$-uniform hypergraphs). When there is no fear of confusion in context, we just say hypergraphs briefly. A hypergraph $H$ without any edge is called \textit{trivial}. The \textit{shadow graph} $G_H$ of a hypergraph $H$ is the graph defined by the pairs of vertices covered by some hyperedge; namely, $G_H$ is the graph on $V(H)$ such that $e\in E(G_H)$ if and only if $e$ is covered by some hyperedge of $H$.

The definition of independence number of hypergraphs is not completely standard. The {\em independence number $\alpha(H)$} is the cardinality of a largest subset $S$ of $V(H)$ that does not contain any edge of $H$ (i.e., the maximum number of vertices in an induced trivial subhypergraph of $H$). Another useful variant important in this paper is the {\em strong independence number $\alpha_1(H)$}, the cardinality of a largest subset $S$ of vertices such that any edge of $H$ intersects $S$ in at most one vertex. In fact, $\alpha_1(H)=\alpha(G_H)$. For example, if $H$ is the Fano plane, $\alpha_1(H)=1, \alpha(H)=4$. For a complete $r$-uniform hypergraph $H$, $\alpha_1(H)=1, \alpha(H)=r-1$. For $r$-uniform hypergraphs these numbers are linked by the following inequality.

\begin{prop}\label{conn}
For any non-trivial $r$-uniform hypergraph $H$, we have $\alpha_1(H)\le \alpha(H)-r+2$.
\end{prop}

\proof{Suppose that $S$ is strongly independent in $H$. Take any $e\in E(H)$ (it satisfies $|S\cap e|\le 1$ by the definition of $S$) and any $v\in e\setminus S$. Then the set $T=(S\cup e)\setminus \{v\}$ is independent and $|T|\ge |S|+r-2$.}\qed\medskip

We need the simplest extension of connectivity from graphs to hypergraphs (no topology involved). A hyperwalk in $H$ is a sequence $v_1,e_1,v_2,e_2,\dots ,v_{t-1},e_{t-1},v_t$, where for all $1\le i<t$ we have $v_i\in e_i$ and $v_{i+1}\in e_i$. We say that $v\sim w$ if there is a hyperwalk from $v$ to $w$. The relation $\sim$ is an equivalence relation, and the subhypergraphs induced by its classes are called the \textit{connected components} of the hypergraph $H$. A vertex $v$ that is not covered by any edge forms a trivial component with one vertex $v$ and no edge. The vertex sets of the connected components of a hypergraph $H$ coincide with the vertex sets of the connected components of~$G_H$.

%A subset $X\subseteq V(H)$ is called {\em connected} if the hypergraph with vertex set $X$ and edge set $\{e\in E(H): e\subseteq X\}$ has one connected component.

Let $H$ be an edge-colored hypergraph. For a subset $S$ of $V(H)$, the subhypergraph induced by $S$ in $H$, that is the hypergraph on the vertex set $S$ with edge set $\{e\in E(H)\mid e\subseteq S\}$, is denoted by $H[S]$. A vertex partition $\mathcal{P}=\{V_1,\dots ,V_l\}$ of $V(H)$ is called a {\em connected partition} if every $H[V_i]$ ($1\le i\le l$) is connected in some color. Similarly, changing partition to cover, we can define {\em connected cover} for every edge-colored hypergraph. (Note that a proper vertex subset of a monochromatic connected component is not necessarily connected, so it may not be possible to use it as a part in a connected partition.) Since partition into vertices is always a connected partition, we can define $cp(H),cc(H)$ for any edge-colored hypergraph $H$ as the minimum number of classes in a connected partition or connected cover, respectively. Observe that for trivial hypergraphs $cc(H)=cp(H)=\alpha(H)=|V(H)|$.

First we will prove the following statement on coverings.

\begin{thm}\label{cover1}
For any $2$-edge-colored hypergraph $H$, we have $cc(H)\le \alpha_1(H)$.
\end{thm}

In fact, the benefit of introducing the concept of $\alpha_1(H)$ is to provide an upper bound on $cc(H)$ in terms of $\alpha(H)$.
From Proposition~\ref{conn} one also gets the following important corollary:

\begin{cor}\label{cover2}
For any $2$-edge-colored non-trivial $r$-uniform hypergraph $H$, we have $cc(H)\le \alpha (H)-r+2$.
\end{cor}

One of our main results is the strengthening of Corollary~\ref{cover2} for partitions.

\begin{thm}\label{partition}
For any $2$-edge-colored non-trivial $r$-uniform hypergraph $H$, we have $cp(H)\le \alpha (H)-r+2$.
\end{thm}

The previous results are sharp. To see this, consider the union of one complete $r$-uniform hypergraph and several isolated vertices.
Observe that the partition version of Theorem~\ref{cover1} does not hold. For example, for the hypergraph $H$ having two edges of size $r$ intersecting in one vertex, one red and one blue, we have $cc(H)=2$ and $cp(H)=r(=\alpha(H)-r+2)$.

It is worth noting that for $r=2$ Theorem~\ref{partition} extends the $k=2$ case of Conjecture~\ref{rysvar}.
Now we have the following general property for $2$-edge-colored graphs.

\begin{thm}\label{newcor}
Any $2$-edge-colored graph $G$ can be partitioned into $\alpha(G)$ monochromatic connected parts.
\end{thm}

\medskip

An edge-coloring of a graph is called a {\em Gallai-coloring} if there is no rainbow triangle in it, i.e. every triangle is colored by at most two colors. Gallai-colorings are natural extensions of $2$-colorings and have been recently investigated in many papers (for references see \cite{GYSUR}). It is known that any Gallai-colored complete graph has a monochromatic spanning tree (see e.g. \cite{GS}). So we have $cp(G)=cc(G)=1$ if $G$ is a Gallai-colored complete graph. Now we focus on Gallai-colored general graphs. Our result is the following:

\begin{thm}\label{mainthm}
For every integer $\alpha$ there exists an integer $g=g(\alpha)$ such that the following holds. If $G$ is a Gallai-colored graph with $\alpha(G)=\alpha$, then $cp(G)\leq g$.
\end{thm}

Theorem~\ref{mainthm} extends the result proved by Gy\'arf\'as, Simonyi and T\'oth \cite{GST} that in any Gallai coloring of a graph $G$, $cc(G)$ is bounded in terms of $\alpha(G)$. We shall also improve on a result in \cite{GST} about dominating sets of multipartite digraphs.


\section{Partitions of $2$-edge-colored hypergraphs, proof of Theorem~\ref{partition}}

We first prove the cover version.

\begin{proof}[Proof of Theorem~\ref{cover1}]
Let $H$ be a hypergraph $2$-edge-colored with red and blue. For every vertex $v\in V(H)$ let $R(v)$, $B(v)$ denote the monochromatic connected components containing $v$ in the hypergraphs of the red and blue edges, respectively. (One or both can be a single component containing $v$.)

From $H$ we construct a bipartite graph $\mathcal{G}$ with bipartition $V(\mathcal{G})=(\mathcal{R},\mathcal{B})$, where $\mathcal{R}=\{R(v)|v\in V(H)\}$, $\mathcal{B}=\{B(v)|v\in V(H)\}$ and with edge set $E(\mathcal{G})=\{R(v)B(v)| v\in V(H)\}$. By the construction, note that $|E(\mathcal{G})|=|V(H)|$ and $\mathcal{G}$ may contain multiple edges. Also we can regard an edge in $E(\mathcal{G})$ as a vertex in $H$.

Notice that for any two independent edges $e=R(v)B(v)$, $e'=R(u)B(u)\in E(\mathcal{G})$, there is no monochromatic connected component containing $v$ and $u$, and hence there is no edge in $H$ containing both $v$ and $u$. Therefore the maximum number of independent edges in $\mathcal{G}$, $\nu(\mathcal{G})$, satisfies $\nu(\mathcal{G})\le \alpha_1(H)$.

By K\"{o}nig's theorem, the edges of $\mathcal{G}$ have a transversal of $\nu(\mathcal{G})$ vertices, i.e., there is a subset $T\subseteq V(\mathcal{G})$ such that $|T|=\nu(\mathcal{G})$ and $T$ intersects all edges of $\mathcal{G}$ in at least one vertex. Then the monochromatic components of $H$ corresponding to the vertices of $T$ form a desired covering of $V(H)$.
\end{proof}

%\begin{rem}
Let us remark that Conjecture~\ref{rysvar} for $k=2$ (its proof is implicitly in \cite{G,GS}) implies Theorem~\ref{cover1} directly as follows. The shadow graph $G_H$ of $H$ can be covered by $\alpha(G_H)=\alpha_1(H)$ monochromatic connected components and so $cc(H)\le\alpha_1(H)$ also holds.
%\end{rem}

Next, we turn to the proof of the partition version.

\begin{proof}[Proof of Theorem~\ref{partition}.]
Let $H$ be a non-trivial $r$-uniform hypergraph with independence number $\alpha (H)$. The proof goes by induction on $\alpha(H)$. In the base case, when $\alpha(H)=r-1$, i.e. $H$ is a $2$-edge-colored complete $r$-uniform hypergraph, it follows from Corollary~\ref{cover2} that one monochromatic component covers the vertices.

Suppose $\alpha(H)>r-1$. By Corollary~\ref{cover2}, $V(H)$ can be covered by the vertices of $p$ red components, $R_{1},\dots ,R_{p}$, and $q$ blue components, $B_{1},\dots ,B_{q}$, so that
\begin{equation}\label{1}
p+q\leq \alpha(H)-r+2.
\end{equation}
We may assume that $p,q$ are both positive, since if one of them is zero, we already have the desired partition in the other color. Set $R=(\bigcup_{1\leq i\leq p}R_{i})\setminus (\bigcup_{1\leq i\leq q}B_{i})$ and $B=(\bigcup_{1\leq i\leq q}B_{i})\setminus (\bigcup_{1\leq i\leq p}R_{i})$. If $R$ or $B$ is empty, we have again the required partition. Thus we may assume that both $R$ and $B$ are non-empty, so $\alpha (H[R])\ge 1$, and $\alpha (H[B])\ge 1$. Observe that
\begin{equation}\label{2}
\alpha (H[R])+\alpha (H[B])\leq \alpha (H)
\end{equation}
since no edge of $H$ can meet both $R$ and $B$. Therefore $\alpha(H[B])\le \alpha(H)-1$ and $\alpha(H[R])\le \alpha(H)-1$.
If $H[R]$ is non-trivial, then $cp(H[R])\le \alpha(H[R])-r+2$ by the inductive hypothesis, but if $H[R]$ is trivial then $cp(H[R])=|R|=\alpha(H[R])$. Similarly, if $H[B]$ is non-trivial, then $cp(H[B])\le \alpha(H[B])-r+2$, if $H[B]$ is trivial then $cp(H[B])=\alpha(H[B])$.

\medskip

\textbf{Case 1.} $H[R]$ is non-trivial (and $H[B]$ is either non-trivial or trivial).

Thus $R$ (the vertex set of $H[R]$) has a connected partition $\mathcal{P}_R$ into at most $\alpha(H[R])-r+2$ parts. The set $B$ (the vertex set of $H[B]$) has a connected partition $\mathcal{P}_B$ into at most $\alpha(H[B])$ parts. Hence $\mathcal{P}_R\cup \{B_1, \dots , B_q\}$ and $\mathcal{P}_B\cup \{R_1, \dots , R_p\}$ are two connected partitions on $V(H)$. Using (\ref{1}),(\ref{2}) we have
$$(|\mathcal{P}_R|+q)+(|\mathcal{P}_B|+p)\le (\alpha(H[R])-r+2) + \alpha(H[B]) + p+q\le 2(\alpha (H)-r+2),$$ therefore one of the previous connected partitions has at most $\alpha(H)-r+2$ parts, as desired.

The case when $H[B]$ is non-trivial goes similarly.

\medskip

\textbf{Case 2.} $H[R]$ and $H[B]$ are both trivial.

Assume $p\ge q$, and select a vertex $v$ from $R$, without loss of generality $v\in R_p$. Observe that no blue edge contains $v$, because $H[R]$ is trivial. Hence every edge containing $v$ is in $R_p$, implying that $\alpha(H\setminus R_p)\le \alpha(H)-1$. If $p>1$ then $H\setminus R_p$ is non-trivial, thus by induction $H\setminus R_p$ has a connected partition with at most $(\alpha(H)-1)-r+2$ parts, adding $R_p$ we obtain the required partition for $H$.
We conclude $p=q=1$.

Let $S$ be a maximal (non-extendable) independent set of $H$ in the form $R\cup B\cup M$. By definition of $S$ (and as $H$ is non-trivial) there exists a hyperedge intersecting $M\cup R$ or $M\cup B$ in exactly $r-1$ vertices (since no edge can intersect both $R$ and $B$), assume the former. Therefore $r\le |M|+|R|+1$, this yields
$$\alpha (H)-r+2 \ge |S|-r+2 = |R|+|B|+|M|-r+2 \ge |R|+|B|+|M| - (|M|+|R|+1) + 2 = |B|+1,$$
thus the red component $R_1$ and vertices of $B$ gives a partition of $H$ into at most $\alpha (H)-r+2$ connected parts.
\end{proof}


\section{Partitions of Gallai-colored graphs, proof of Theorem~\ref{mainthm}}

We need some notions introduced in \cite{GST}.
If $D$ is a digraph and $U\subseteq V(D)$ is a subset of its vertex set then $N_+(U)=\{v\in V(D)| \exists u\in U \ (u,v)\in E(D)\}$ is the \textit{outneighborhood} of $U$.
% The \textit{closed outneighborhood} $N_+[U]$ of $U$ is meant to be the set $U\cup N_+(U)$.
A multipartite digraph is a digraph $D$ whose vertices are partitioned into classes $A_1,\dots ,A_t$ of independent vertices. Let $S\subseteq [t]$. A set $U=\cup_{i\in S}A_i$ is called a \textit{dominating set} of size $|S|$ if for any vertex $v\in \cup_{i\notin S}A_i$ there is a $w\in U$ such that $(w,v)\in E(D)$. The smallest $|S|$ for which a multipartite digraph $D$ has a dominating set $U=\cup_{i\in S}A_i$ is denoted by $k(D)$. Let $\beta(D)$ be the cardinality of the largest independent set of $D$ whose vertices are from different partite classes of $D$. (We sometimes refer to them as \textit{transversal independent sets}.) An important special case is when $|A_i|=1$ for each $i\in [t]$. Then it follows that $\beta(D)=\alpha(D)$ and $k(D)=\gamma(D)$, the usual domination number of $D$, the smallest number of vertices in $D$ whose closed outneighborhoods cover $V(D)$. In \cite{GST}, the following are shown:

\begin{thm}[\cite{GST}]\label{thm2}
Suppose that $D$ is a multipartite digraph such that $D$ has no cyclic triangle. If $\beta (D)=1$ then $k(D)=1$ and if $\beta (D)=2$ then $k(D)\leq 4$.
\end{thm}

\begin{thm}[\cite{GST}]\label{GSTresult}
For every integer $\beta$ there exists an integer $h=h(\beta)$ such that the following holds. If $D$ is a multipartite digraph without cyclic triangles and $\beta(D)=\beta$, then $k(D)\le h$.
\end{thm}

To keep the paper self-contained we give a proof for this statement with a slightly better bound than the one presented in \cite{GST}.

\begin{proof}[Proof of Theorem~\ref{GSTresult}]
Set $h(1)=1$, $h(2)=4$ and $h(\beta )=\beta +(\beta +1)h(\beta -1)$ for $\beta \geq 3$.
The proof goes by induction on $\beta $. By Theorem~\ref{thm2}, we may assume that $\beta \geq 3$ and the theorem is proved for $\beta -1$. Let $D$ be a multipartite digraph with no cyclic triangle and $\beta (D)=\beta $. For each $x\in V(D)$, let $Z^{(x)}$ be the partite class containing $x$. Let $k_{1},\dots ,k_{\beta }$ be $\beta $ vertices of $D$, each from a different partite class, such that $|N_{+}(\{k_{1},\dots ,k_{\beta }\})\cup (\bigcup _{1\leq i\leq \beta }Z^{(k_{i})})|$ is maximal. Let $\mathcal{K}_{1}=\{Z^{(k_{i})}\mid 1\leq i\leq \beta \}$. For each partite class $Z\not\in \mathcal{K}_{1}$, let $Z_{0}=Z\cap N_{+}(\bigcup_{1\leq i\leq \beta }Z^{(k_{i})})$. For every $i$ with $1\leq i\leq \beta $, let $Z_{i}$ be the set of vertices in $Z\setminus Z_{0}$ that are not sending an edge to $k_{i}$, but sending an edge to $k_{j}$ for all $j<i$. Finally, let $Z_{\beta +1}$ denote the remaining part of $Z$, the set of those vertices of $Z$ that do not belong to $N_{+}(\bigcup_{1\leq i\leq \beta }Z^{(k_{i})})$ and send an edge to all vertices $k_{1},\dots ,k_{\beta }$. (We will refer to the set $Z_{i}$ as the $i$-th part of $Z$.) The subgraph $D_{i}$ of $D$ induced by the $i$-th parts of the partite classes of $D\setminus(\bigcup_{1\leq i\leq \beta }Z^{(k_{i})})$ is also a multipartite digraph with no cyclic triangle. For every $i$ with $1\leq i\leq \beta $, since adding $k_{i}$ to any transversal independent set of $D_{i}$ we get a larger transversal independent set, it follows that $\beta (D_{i})\leq \beta -1$.

Suppose that $\beta (D_{\beta +1})\geq \beta $. Let $\{l_{1},\dots ,l_{\beta }\}$ be a transversal independent set of $D_{\beta +1}$.

\begin{clm}
For every $x\in \big(N_{+}(\{k_{1},\dots ,k_{\beta }\})\cup (\bigcup_{1\leq i\leq \beta }Z^{(k_{i})})\big)\setminus(\bigcup_{1\leq i\leq \beta }Z^{(l_{i})})$, we have $x\in N_{+}(\{l_{1},\dots ,l_{\beta }\})$.
\end{clm}

\proof{
Suppose that $x\in N_{+}(\{k_{1},\dots ,k_{\beta }\})\setminus\bigcup_{1\leq i\leq \beta }Z^{(l_{i})}$. Then there exists an integer $1\leq i_{0}\leq \beta $ such that $(k_{i_{0}},x)\in E(D)$. Recall that $(l_{i},k_{i_{0}})\in E(D)$ for every $1\leq i\leq \beta $. Since $\{x,l_{1},\dots ,l_{\beta }\}$ is not independent and $D$ has no cyclic triangle, $x\in N_{+}(\{l_{1},\dots ,l_{\beta }\})$, as desired. Thus we may assume that $x\in \bigcup_{1\leq i\leq \beta }Z^{(k_{i})}$. Recall that $(x,l_{i})\not\in E(D)$ for every $1\leq i\leq \beta $. Since $\{x,l_{1},\dots ,l_{\beta }\}$ is not independent, $x\in N_{+}(\{l_{1},\dots ,l_{\beta }\})$.}\qed\medskip

Thus we have $N_{+}(\{k_{1},\dots ,k_{\beta }\})\cup (\bigcup_{1\leq i\leq \beta }Z^{(k_{i})})\subseteq N_{+}(\{l_{1},\dots ,l_{\beta }\})\cup (\bigcup_{1\leq i\leq \beta }Z^{(l_{i})})$. Since $l_{1}\in \big(N_{+}(\{l_{1},\dots ,l_{\beta }\})\cup (\bigcup_{1\leq i\leq \beta }Z^{(l_{i})})\big)\setminus\big(N_{+}(\{k_{1},\dots ,k_{\beta }\})\cup (\bigcup_{1\leq i\leq \beta }Z^{(k_{i})})\big)$, it follows
$$\left|N_{+}(\{k_{1},\dots ,k_{\beta }\})\cup \left(\bigcup_{1\leq i\leq \beta }Z^{(k_{i})}\right)\right|<\left|N_{+}(\{l_{1},\dots ,l_{\beta }\})\cup \left(\bigcup_{1\leq i\leq \beta }Z^{(l_{i})}\right)\right|,$$
which contradicts the choice of $k_{1},\dots ,k_{\beta }$. Thus $\beta (D_{\beta +1})\leq \beta -1$.

By induction on $\beta $, $D_{i}$ ($1\leq i\leq \beta +1$) can be dominated by at most $h(\beta -1)$ partite classes. Let $\mathcal{K}_{2}$ be the appropriate $(\beta +1)h(\beta -1)$ partite classes such that $\bigcup_{Z\in \mathcal{K}_{2}}Z$ dominates $\bigcup_{1\leq i\leq \beta +1}V(D_{i})$. Hence we constructed a dominating set $\bigcup_{Z\in \mathcal{K}_{1}\cup \mathcal{K}_{2}}Z$ of $D$ containing at most $\beta +(\beta +1)h(\beta -1)$ partite classes.

This completes the proof of Theorem~\ref{GSTresult}.
\end{proof}

To prepare the proof of Theorem~\ref{mainthm} we need the following lemma about trees.

\begin{lem}\label{fixprob}
Let $t\geq 1$ be an integer. Let $T$ be a tree of order at least $t$. Then there exist two sets $R\subseteq C\subseteq V(T)$ such that $|R|=t$, $|C|\leq 2t$, $T[C]$ is connected, and either $T\setminus R$ is connected or $V(T)=R$.
\end{lem}

\begin{proof}
If $|V(T)|=t$, then the lemma holds by choosing $R=C=V(T)$. Thus we may assume that $|V(T)|\geq t+1$. For each edge $xy\in E(T)$, let $T^{x}_{xy}$ denote the component of $T\setminus xy$ containing $x$. Note that $|\{x\}\cup (\bigcup_{y\in N(x)}V(T^{y}_{xy}))|=|V(T)|\geq t+1$ for every $x\in V(T)$. We choose a vertex $x_{0}\in V(T)$ and a subset $A_{0}\subseteq N(x_{0})$ such that
\begin{description}
\item{(i)} $|\{x_{0}\}\cup (\bigcup_{y\in A_{0}}V(T^{y}_{x_{0}y}))|\geq t+1$, and
\item{(ii)} subject to (i), $|\{x_{0}\}\cup (\bigcup_{y\in A_{0}}V(T^{y}_{x_{0}y}))|$ is minimized.
\end{description}
By the definition of $x_{0}$ and $A_{0}$, we have $A_{0}\not=\emptyset$. Set $a=|\{x_{0}\}\cup (\bigcup_{y\in A_{0}}V(T^{y}_{x_{0}y}))|$.

\begin{clm}\label{ale2t}
$a\leq 2t$.
\end{clm}

\proof{
Suppose that $a\geq 2t+1$. If $|A_{0}|=1$, say $A_{0}=\{y_{0}\}$, then $|\{y_{0}\}\cup (\bigcup_{y\in N(y_{0})\setminus\{x_{0}\}}V(T^{y}_{y_{0}y}))|=a-1(\geq t+1)$, which contradicts the definition of $x_{0}$ and $A_{0}$. Thus $|A_{0}|\geq 2$. Then there exists a vertex $y_{1}\in A_{0}$ such that $|V(T^{y_{1}}_{x_{0}y_{1}})|\leq (a-1)/2$. Hence
$$|\{x_{0}\}\cup \Big(\bigcup_{y\in A_{0}\setminus\{y_{1}\}}V(T^{y}_{x_{0}y})\Big)|=a-|V(T^{y_{1}}_{x_{0}y_{1}})|\geq a-\frac{a-1}{2}=
\frac{a+1}{2}\geq \frac{2t+2}{2}=t+1,$$
which contradicts the definition of $A_{0}$.
}\qed\medskip

Write $\bigcup_{y\in A_{0}}V(T^{y}_{x_{0}y})=\{x_{1},\dots ,x_{a-1}\}$, we may assume that the elements of this set are ordered in a non-increasing order by the distance from $x_0$. Let $C=\{x_{0}\}\cup (\bigcup_{y\in A_{0}}V(T^{y}_{x_{0}y}))$ and $R=\{x_{i}\mid 1\leq i\leq t\}$. Then $|R|=t$, $|C|\leq 2t$ and both $T[C]$ and $T\setminus R$ are connected.
\end{proof}

Now we are ready to prove Theorem~\ref{mainthm}. Let $g(1)=1$ and $g(\alpha )=\max \{h(\alpha )(\alpha ^{2}+\alpha -1), 2h(\alpha )g(\alpha -1)+h(\alpha )+1\}$ for $\alpha \geq 2$.

\begin{proof}[Proof of Theorem~\ref{mainthm}.] We show that $cp(G)\le g(\alpha(G))$ with the function $g$ defined above. We may assume that $|V(G)|\geq g(\alpha )$. We proceed by induction on $\alpha $. If $\alpha =1$, then $G$ is complete, and hence, as mentioned in the introduction, there is a connected monochromatic spanning subgraph of $G$, as desired. Thus we may assume that $\alpha \geq 2$. Let $T_{0}$ be a maximum connected spanning monochromatic subtree of $G$ in the coloring $c$. We may assume that every edge of $T_{0}$ has color $1$. It was proved in \cite{GS} that the largest monochromatic subtree in every Gallai-coloring of a graph $G$ has at least $|V(G)|(\alpha^2+\alpha-1)^{-1}$ vertices. Using this, since $|V(G)|\geq g(\alpha )\geq h(\alpha )(\alpha ^{2}+\alpha -1)$, $|V(T_{0})|\geq h(\alpha )$ follows. By Lemma~\ref{fixprob}, there exist two sets $R$ and $C$ with $R\subseteq C\subseteq V(T_{0})$ such that $|R|=h(\alpha )$, $|C|\leq 2h(\alpha )$, $T_{0}[C]$ is connected, and either $T_{0}\setminus R$ is connected or $V(T_{0})=R$. Write $C=\{u_{1},\dots ,u_{m}\}$. Note that $h(\alpha )\leq m\leq 2h(\alpha )$. We may assume that $R=\{u_{1},\dots ,u_{h(\alpha )}\}$. For every $i$ with $1\leq i\leq m$, let $U_{i}$ be the set of vertices in $V(G)\setminus V(T_{0})$ that are not adjacent to $u_{i}$, but adjacent to $u_{j}$ for all $j<i$. For every $i$ with $1\leq i\leq m$, we have $\alpha (G[U_{i}])\leq \alpha -1$ because adding $u_{i}$ to any independent set of $G[U_{i}]$ we get a larger independent set. By the inductive assumption, for every $i$ with $1\leq i\leq m$, there exists a partition $\mathcal{P}_{i}$ of $U_{i}$ such that $|\mathcal{P}_{i}|\leq g(\alpha -1)$ and, for every $U\in \mathcal{P}_{i}$, $G[U]$ has a connected spanning monochromatic subgraph with respect to $c$.

Let $U_{0}=V(G)\setminus\left(V(T_{0})\cup \left( \bigcup_{1\leq i\leq m}U_{i}\right) \right) $. Recall that $T_{0}[C]$ is a connected monochromatic tree and $c$ is a Gallai-coloring of $G$. For every $v\in U_{0}$, since $v$ is adjacent to every vertex of $C$, all of $E(v,C)$ are colored with the same color, say $c_{v}$. Note that $c_{v}\not=1$ for every $v\in U_{0}$ by the definition of $T_{0}$. Let $l$ be the number of colors used on edges of $E(U_{0},C)$. We may assume that $2,\dots ,l+1$ are the colors used on these edges. For each $i$ with $2\leq i\leq l+1$, let $A_{i}=\{v\in U_{0}\mid c_{v}=i\}$. Note that $\{A_{2},\dots ,A_{l+1}\}$ is a partition of $U_{0}$. Since $c$ is a Gallai coloring of $G$, each edge between $A_{i}$ and $A_{j}$ is colored with either color $i$ or $j$ for $i,j$ with $2\leq i,j\leq l+1$ and $i\not=j$.

\bigskip

We construct the multipartite digraph $D$ on $U_{0}$ as follows:
\begin{description}
\item{(i)} $A_{2},\dots ,A_{l+1}$ are the partition classes of $D$.
\item{(ii)} For $i,j$ with $2\leq i,j\leq l+1$ and $i\not=j$, $v\in A_{i}$ and $v'\in A_{j}$, let $(v,v')\in E(D)$ if and only if $vv'\in E(G)$ and $c(vv')=i$.
\end{description}
Note that $\beta (D)\leq \alpha $ and $D$ has no cyclic triangle. By Theorem~\ref{GSTresult}, there exist at most $h(\alpha )$ partite classes dominating $V(D)$, say $B_{1},\dots ,B_{p}$. Let $B_{p+1}=\dots =B_{h(\alpha )}=\emptyset $. For every $i$ with $1\leq i\leq h(\alpha )$, let $B'_{i}$ be the set of vertices in $U_{0}\setminus\left( \bigcup_{1\leq i\leq h(\alpha )}B_{i}\right) $ that are dominated by $B_{i}$, but not dominated by $B_{j}$ for all $j<i$, and let $B''_{i}=\{u_{i}\}\cup B_{i}\cup B'_{i}$. For each $i$ with $1\leq i\leq h(\alpha )$, note that $G[B''_{i}]$ has a connected monochromatic spanning subgraph. Therefore $\mathcal{P}=\{V(T_{0})\setminus R,B''_{1},\dots ,B''_{h(\alpha )}\}\cup \left(\bigcup_{1\leq i\leq m}\mathcal{P}_{i}\right)$ is a partition of $V(G)$ satisfying that $G[U]$ has a connected spanning monochromatic subgraph with respect to $c$ for every $U\in \mathcal{P}$. Furthermore,
\begin{eqnarray*}
|\mathcal{P}|&\leq& (h(\alpha )+1)+\sum_{1\leq i\leq m}|\mathcal{P}_{i}| \leq (h(\alpha )+1)+\sum_{1\leq i\leq m}g(\alpha -1) =\\
&=& (h(\alpha )+1)+mg(\alpha -1)\le (h(\alpha )+1)+2h(\alpha )g(\alpha -1).
\end{eqnarray*}

This completes the proof of Theorem~\ref{mainthm}.
\end{proof}


\section{Conclusion, open problems}

The quantities $cc(G),cp(G)$ can be far apart, even for $2$-edge-colored graphs. For example, let $G$ be a star with $2t$ edges and color $t$ edges in both colors. Then $cc(G)=2, cp(G)=t+1$. Nevertheless, the extension of Conjecture~\ref{rysvar} to partitions of complete graphs has been formulated in \cite{EGP}. Probably this remains true for Ryser's conjecture in general.

\begin{conj}\label{ryspar}
If the edges of $G$ are colored with $k$ colors then $cp(G)\le \alpha(G)(k-1)$.
\end{conj}

As mentioned before, Conjecture~\ref{ryspar} is proved for $\alpha(G)=1, k=3$ in \cite{EGP}. Note that $cc(G)\le \alpha(G)k$ is obvious for any $k$-edge-colored graph $G$. For $k$-edge-colored complete graphs $K$, Haxell and Kohayakawa \cite{HK} proved $cp(K)\le k$, this is just one off from Conjecture~\ref{ryspar}. It would be interesting to attack the case $k=3$ in Conjecture~\ref{ryspar} since its cover version, Conjecture~\ref{rysvar} is available (\cite{A}).

As mentioned in the introduction, Kir\'aly \cite{K} solved completely the cover problem for complete $r$-uniform complete hypergraphs ($r\ge 3$). (The number of colors $k$ can be arbitrary.) It seems that the analogue for partition is not easy. A first test case might be the following.

\begin{prob}
Suppose that a complete $3$-uniform hypergraph $H$ is $6$-edge-colored. Is it true that $cp(H)\le 2$? ($cc(H)\le 2$.)
\end{prob}

In general, the cover problem of hypergraphs for general $\alpha$ or $\alpha_1$ seems difficult, even to find the right conjecture is a challenge. We shall address this question in \cite{FFGT}.

%\newpage

\begin{thebibliography}{99}

\bibitem{A} R.~Aharoni, Ryser's conjecture for tripartite $3$-graphs, {\it Combinatorica}, {\bf 21} (2001), 1--4.

\bibitem{AH} R.~Aharoni, P.~Haxell, Hall's theorem for hypergraphs, {\it J. Graph Theory}, {\bf 35} (2000), 83--88.

\bibitem{EGP} P.~Erd\H{o}s, A.~Gy\'{a}rf\'{a}s, L.~Pyber, Vertex coverings by monochromatic cycles and trees, {\it J. Combin. Theory Ser. B}, {\bf 51} (1991), 90--95.

\bibitem{FFGT} S.~Fujita, M.~Furuya, A.~Gy\'{a}rf\'{a}s, \'{A}.~T\'{o}th, Vertex covers of edge-colored hypergraphs by monochromatic connected parts, {\it in preparation}.

\bibitem{G} A.~Gy\'{a}rf\'{a}s, Partition coverings and blocking sets in hypergraphs (in Hungarian), {\it Commun. Comput. Autom. Inst. Hungar. Acad. Sci.}, {\bf 71} (1977), 62pp.

\bibitem{GYSUR} A.~Gy\'arf\'as, Large monochromatic components in edge colorings of graphs: a survey, In: Alexander Soifer (editor) Ramsey Theory: Yesterday, Today and Tomorrow. New York; London: Birkhauser Verlag, 2010, 77--96.

\bibitem{GS} A.~Gy\'{a}rf\'{a}s, G.~S\'{a}rk\"{o}zy, Gallai colorings of non-complete graphs, {\it Discrete Math.}, {\bf 310} (2010), 977--980.

\bibitem{GST} A.~Gy\'{a}rf\'{a}s, G.~Simonyi, \'{A}.~T\'{o}th, Gallai colorings and domination in multipartite digraphs, {\it J. Graph Theory, in press} (DOI: 10.1002/jgt.20646).

\bibitem{H} P.~Haxell, A note on a conjecture of Ryser, {\it Periodica Math. Hung.}, {\bf 30} (1995), 73--79.

\bibitem{HK} P.~Haxell, Y.~Kohayakawa, Partitioning by monochromatic trees, {\it J. Combin. Theory Ser. B}, {\bf 68} (1996), 218--222.

\bibitem{HE} J.~R.~Henderson, Permutation Decomposition of (0-1)-Matrices and Decomposition Transversals, Ph.D. thesis, Caltech, 1971.

\bibitem{K} Z.~Kir\'{a}ly, Monochromatic components in edge-colored complete uniform hypergraphs, {\it Electronic Notes in Discrete Mathematics}, {\bf 38C} (2011), 517--521.

\bibitem{SZT} E.~Szemer\'{e}di, Zs.~Tuza, Upper bound for transversals of tripartite hypergraphs, {\it Periodica Math. Hung.}, {\bf 13} (1982), 321--323.

%\bibitem{BT} S. Bessy and S. Thomass\'e, Partitioning a graph into a cycle and an anticycle, a proof of Lehel's conjecture, {\it J. Combin. Theory Ser. B}, {\bf 100} (2010), 176--180.

%\bibitem{S} G.~S\'ark\"ozy, Monochromatic cycle partitions of edge-colored graphs, {\it J. Graph Theory}, {\bf 66} (2010), 57--64.

%\bibitem{T} Zs.~Tuza, On special cases of Ryser's conjecture, manuscript.

\end{thebibliography}

\end{document}