\documentclass[12pt]{article} \usepackage{e-jc} \specs{P2.27}{22(2)}{2015} %\usepackage{amsmath} %\usepackage{amssymb} %\usepackage[dvips]{graphics} \usepackage{amsthm,amssymb,amsmath,enumerate,graphicx} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} %\topmargin=-2mm %\oddsidemargin=-3mm %\evensidemargin=0pt %\textheight=220mm %\textwidth=166mm %\parskip=0.5\baselineskip %\parskip=1.7mm % NOTE - NEED plainpages=false,pdfpagelabels % OLD had plainpages-true and no pdfpagelabels in the list %BRING BACK %\usepackage[pdftex,bookmarksnumbered,colorlinks,a4paper,hypertexnames=true,linkcolor=blue,plainpages=false,pdfpagelabels,citecolor=red,urlcolor=blue] %\usepackage{amsthm,amssymb,amsmath,enumerate,graphics} \newtheorem{theorem}{Theorem}[section] %\newtheorem{theorem}{Theorem} %\newtheorem{definition}[theorem]{Definition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{assertion}[theorem]{Assertion} \newtheorem{observation}[theorem]{Observation} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{notation}[theorem]{Notation} \newtheorem{remark}[theorem]{Remark} \newtheorem{definition}[theorem]{Definition} \newcommand{\ca}{\mathcal A} \newcommand{\cb}{\mathcal B} \newcommand{\cc}{\mathcal C} \newcommand{\cd}{\mathcal D} \newcommand{\ce}{\mathcal E} \newcommand{\cf}{\mathcal F} \newcommand{\cg}{\mathcal G} \newcommand{\ch}{\mathcal H} \newcommand{\ci}{\mathcal I} \newcommand{\cj}{\mathcal J} \newcommand{\ck}{\mathcal K} \newcommand{\cl}{\mathcal L} \newcommand{\cm}{\mathcal M} \newcommand{\cn}{\mathcal N} \newcommand{\co}{\mathcal O} \newcommand{\cp}{\mathcal P} \newcommand{\cq}{\mathcal Q} \newcommand{\cs}{\mathcal S} \newcommand{\cgr}{\mathcal R} \newcommand{\ct}{\mathcal T} \newcommand{\cu}{\mathcal U} \newcommand{\cv}{\mathcal V} \newcommand{\cx}{\mathcal X} \newcommand{\cy}{\mathcal Y} \newcommand{\cz}{\mathcal Z} \newcommand{\cw}{\mathcal W} %\pagestyle{empty} \title{\bf Cooperative colorings\\ and independent systems of representatives} %\makeatletter %\renewcommand{\@oddhead}{DP120100197} (Aharoni, Howard, Meshulam) %\makeatother \author{Ron Aharoni\thanks{Research supported by BSF grant no. 2006099, by ISF grant no. $1581/12$ and by the Discount Bank Chair at the Technion.}\\ \small Department of Mathematics\\[-0.8ex] \small Technion, Israel\\[-0.8ex] \small\tt raharoni@gmail.com\\ \and Ron Holzman\thanks{Research was partly done while the second author was visiting the Department of Mathematical Sciences, Carnegie Mellon University.}\\ \small Department of Mathematics\\[-0.8ex] \small Technion, Israel\\[-0.8ex] \small\tt holzman@tx.technion.ac.il\\ \and David Howard\thanks{Research supported by ISF grants nos 779/08, 503/11, 859/08 and BSF grant no 2006099, and by a Technion postdoctoral fellowship.}\\ \small Departments of Mathematics\\[-0.8ex] \small Technion, Israel and Colgate University, USA\\[-0.8ex] \small\tt dmhoward@colgate.edu\\ \and Philipp Spr\"ussel\thanks{Research supported by Haifa University postdoctoral fellowship.}\\ \small Departments of Mathematics\\[-0.8ex] \small University of Haifa, Israel and Graz University of Technology, Austria\\[-0.8ex] \small\tt spruessel@math.tugraz.at } \date{\dateline{Jun 30, 2012}{May 11, 2015}{May 22, 2015}\\ \small Mathematics Subject Classifications: 05C15, 05C69} \begin{document} \maketitle \begin{abstract} We study a generalization of the notion of coloring of graphs, similar in spirit to that of list colorings: a \emph{cooperative coloring} of a family of graphs $G_1,G_2, \ldots,G_k$ on the same vertex set $V$ is a choice of independent sets $A_i$ in $G_i$ ($1 \le i \le k)$ such that $\bigcup_{i=1}^kA_i=V$. This notion is linked (with translation in both directions) to the notion of ISRs, which are choice functions on given sets, whose range belongs to some simplicial complex. When the complex is that of the independent sets in a graph $G$, an \emph{ISR} for a partition of the vertex set of $G$ into sets $V_1,\ldots ,V_n$ is a choice of a vertex $v_i \in V_i$ for each $i$ such that $\{v_1,\ldots,v_n\}$ is independent in $G$. Using topological tools, we study degree conditions for the existence of cooperative colorings and of ISRs. A sample result: Three cycles on the same vertex set have a cooperative coloring. \end{abstract} \section{Cooperative colorings} For a graph $G$ denote by $\ci(G)$ the complex (closed down hypergraph) of independent sets in $G$. A {\em $k$-coloring} of $G$ is a choice of disjoint sets $A_1, A_2, \ldots ,A_k$ in $\ci(G)$ such that $\bigcup_{i=1}^k A_i=V(G)$. It is possible to require that the sets $A_i$ belong to prescribed induced subgraphs of $G$ - this is the idea behind the notion of {\em list coloring}. Given subsets $C_i,~i=1,\ldots,k$ of $V(G)$, a list coloring is a decomposition of $V(G)$ into sets $A_i \in \ci(G[C_i]),~i=1,\ldots,k$ ($C_i$ is the set of vertices in whose list color $i$ appears). In another setting, there are given general graphs $G_i$ on the same vertex set $V$, and each set $A_i$ in the partition is taken from $\ci(G_i)$. This is called {\em cooperative coloring}. Combining the two, we get a still more general setting, in which the graphs are each on a different set of vertices, in which case the decomposition into the sets $A_i$ is called a {\em cooperative list coloring}. Here it is, more formally: \begin{definition} A family of (not necessarily distinct) graphs $G_1,G_2,\ldots,G_k$ with respective vertex sets $V(G_1),V(G_2),\ldots,V(G_k) \subseteq V$ is called a \emph{cooperative list coloring} system, or CLC-system for short. The \emph{multiplicity} of the system, denoted by $m$, is the minimum over all $v \in V$ of $|\{i: v \in V(G_i)\}|$. A \emph{cooperative list coloring} then is a choice of independent sets $A_i$ in $G_i$ ($1 \le i \le k$) such that $\bigcup_{i=1}^kA_i=V$. If $G_i=G[C_i]$ for a fixed $G$, then the system is called a {\em list coloring} system. If all sets $V(G_i)$ are the same set $V$, then the system is called a {\em cooperative coloring system}, and a choice of $A_i$ as above is called a {\em cooperative coloring}. %and is written $(G;C_1, \ldots, C_k)$. \end{definition} In an even more general setting, there are complexes $\cc_1,\ldots, \cc_k$ on the same vertex $V$, and a cooperative coloring is a partition of $V$ into sets $A_i \in \cc_i, ~i=1,\ldots,k$. The list coloring case, of complexes on subsets $C_i$ of $V$, is then obtained as a special case by taking the singleton set of every point not in $C_i$ as not belonging to the complex $\cc_i$. We shall be interested in degree conditions guaranteeing cooperative colorings, in the spirit of the bound $\Delta+1$ on the chromatic number of a graph. The natural conjecture would be that a CLC-system of graphs with maximal degree $d$ and multiplicity $m \ge d+1$ has a cooperative list coloring. In fact, this was conjectured by Reed \cite{reed} in the case of list colorings, but was refuted in \cite{bh}. Below we shall see examples showing that this also fails in the case of cooperative colorings. Yet, these examples refute only the $d+1$ conjecture, and there are no examples known of CLC-systems with $m \ge d+2$ and no cooperative list coloring. \section{Cooperative list coloring systems as layered ISR-systems} The notion of cooperative list colorings is a special case of that of {\em independent systems of representatives}, or ISRs (also called in the literature {\em independent transversals}). This is a generalization of the notion of SDRs (systems of distinct representatives). As in the setting of SDRs, there are given sets $V_i,~1 \le i \le n$, and we wish to find representatives $f(i)=v_i \in V_i$. In the ISR setting the requirement of distinctness is replaced by another type of restriction. A complex $\cc$ is given on $V=\bigcup_{i=1}^nV_i$, and it is required that $\{v_1,\ldots,v_ n\} \in \cc$. The choice function $f$ is then called a $\cc$-{\em SR}. A simple reduction shows that it is enough to consider disjoint $V_i$s: form a distinct copy $v_i$ of $v$ for every appearance of a vertex $v$ in a set $V_i$, and for $p \neq q$ do not include $\{v_p,v_q\}$ in the new complex generated. Henceforth, we assume the $V_i$s are disjoint. Here we study the case where $\cc = \ci(G)$ for some graph $G$ on $V$, and refer to $\cc$-SRs as ISRs. As mentioned, cooperative list colorings are a special case, that of {\em layered} ISRs. In a layered ISR-system, $\bigcup_{i=1}^n V_i = \bigcup_{j=1}^k L_j$, where the $L_j$s are disjoint, $|V_i \cap L_j| \le 1$ for all $i,j$, and $\cc$ is the join of $\cc_j=\cc[L_j]$ (namely $A \in \cc$ if and only if $A \cap L_j \in \cc$ for all $j$). The sets $L_j$ are then called {\em layers}. In the graphic case that we study here, the graph $G$ is the disjoint union of graphs $G_j$ on the layers $L_j$. The translation of cooperative list colorings to layered ISRs is done as follows. Let $G_1,\ldots,G_k$ be given, with respective vertex sets $V(G_1),\ldots,V(G_k) \subseteq V=\{v_1,\ldots,v_n\}$. For $i=1,\ldots,n$ let $V_i = \{(i,j):\, v_i \in V(G_j)\}$, and for $j=1,\ldots,k$ let $L_j = \{(i,j):\, v_i \in V(G_j)\}$. On each layer $L_j$, we have a copy of the corresponding graph $G_j$. An ISR $f$ for this system is equivalent to a cooperative list coloring that decomposes $V$ into the sets $A_j = \{v_\ell:\, f(\ell)=(\ell,j)\}$, $j=1,\ldots,k$. Observe that under this translation, the multiplicity $m$ becomes the minimal size of the $V_i$s. We write $\cj(G_1,\ldots,G_k)$ for the ISR-system constructed in this way. \begin{remark} The idea of this translation first appeared, for the list coloring problem, in \cite{penny01}. \end{remark} The translation above allows to deduce existence results for cooperative list colorings as immediate corollaries of corresponding existence results for ISRs. We list here a few such corollaries, in each case citing the paper where the relevant ISR result appeared. In all items, we consider a CLC-system $G_1, G_2,\ldots, G_k$ of graphs with maximal degree at most $d$ and multiplicity $m$, and the stated conditions are sufficient for the existence of a cooperative list coloring. \begin{enumerate} \item $m \ge 2d$ \cite{penny01}. \item $m \ge d+o(d)$ \cite{ls}. \item $m \ge d+2$ and all $G_i$ are line graphs \cite{aab}. \item $m \ge d+1$ and all $G_i$ are chordal graphs \cite{abz}. \end{enumerate} We note that the ISR results corresponding to items (1), (3) and (4) above were proved for general ISR-systems, not just layered ones, which arise under the translation from CLC-systems. The result corresponding to (2) was proved for so-called locally sparse systems, a subclass of ISR-systems which is still more general than layered systems. The consideration of cooperative list colorings motivates the study of layered ISR-systems. To what extent does the property of being layered allow a relaxation of the size requirement on the $V_i$s for the existence of an ISR? What if, moreover, the layers are full, i.e., $|V_i \cap L_j|=1$ for all $i,j$? (This corresponds to cooperative coloring.) What if, alternatively, the layer-graphs are all induced from the same graph? (This corresponds to list coloring, and was studied in \cite{reed}, \cite{rs}, \cite{bh}.) Of course, if both restrictions apply, we are back to plain graph coloring, and $|V_i| \ge d+1$ suffices. As a curiosity, we note that the translation between cooperative coloring problems and ISR problems goes also in the other direction. Let $(G,(V_i)_{i=1}^n)$ be an ISR-system. Form a cooperative coloring system as follows. First, augment every $V_i$ to $V^*_i$ of size $k:=\max\{|V_\ell|:~1 \le \ell \le n\}$, by adding $k-|V_i|$ vertices that are connected to all vertices of all other $V^*_{\ell}$'s. Denote by $(G^*,(V^*_i)_{i=1}^n)$ the augmented system. Then let $G_1,\ldots,G_{k-1}$ be identical graphs, each consisting of disjoint cliques, a clique on each $V^*_i$. Let $G_k=G^*$. An independent set taken from $G_j~(j 2$. If $|V_i| \ge 2d-1$ for all $i$, then there is an ISR unless $G$ contains at least $2d-1$ connected components isomorphic to $K_{d,d}$. \end{theorem} In order to prove Theorem~\ref{kdd}, we establish the following lower bound on the connectivity of the independence complex of a graph: \begin{theorem}\label{connectivityofG} Let $d>2$. If $G$ has maximal degree at most $d$ and contains no $K_{d,d}$, then \begin{equation*} \eta_H(\ci(G)) \ge \Psi_e(G) \ge \frac{|V(G)|}{2d-1}. \end{equation*} \end{theorem} Before proving Theorem~\ref{connectivityofG}, let us show how it implies Theorem~\ref{kdd}. Indeed, for every $I\subseteq [n]$, let $k_I$ be the number of copies of $K_{d,d}$ contained in $G[V_I]$. Since $\eta_H(\ci(K_{d,d}))=1=\frac{|V(K_{d,d})|-1}{2d-1}$, we obtain by Lemma~\ref{additive} and Theorem~\ref{connectivityofG} \begin{equation*} \eta_H(\ci(G) \upharpoonright V_I) \ge \frac{|V_I|-k_I}{2d-1} \ge |I|-\frac{k_I}{2d-1}. \end{equation*} \noindent Therefore, if $G$ contains fewer than $2d-1$ copies of $K_{d,d}$, then $k_I <2d-1$, and thus $\eta_H(\ci(G) \upharpoonright V_I)> |I|-1$, and since $\eta_H$ is integral this means that $\eta_H(\ci(G) \upharpoonright V_I)\ge |I|$. By Theorem~\ref{ah} there exists an ISR. \begin{proof}[Proof of Theorem~\ref{connectivityofG}] We may clearly assume that $G$ is connected. We will prove the theorem by showing that in the game that defines $\Psi_e(G)$, CON can force NON to either create an isolated vertex or spend at least $\frac{|V(G)|}{2d-1}$ explosion steps to destroy all vertices. In the first step $2d$ vertices may be removed in an explosion, but from that step on there is at each step a vertex of degree at most $d-1$, and as we may assume that it is not isolated, CON can choose an edge $uv$ with $|N(u)\cup N(v)|\le 2d-1$. This implies that $\Psi_e(G) \ge \frac{|V(G)|-1}{2d-1}$, and we may assume that equality holds (otherwise we are done). Therefore, the first step must be an explosion destroying $2d$ vertices, and any subsequent explosion step must remove $2d-1$ vertices. We may assume that $G$ is $d$-regular and triangle-free, otherwise CON can choose his first edge so as to prevent NON from exploding $2d$ vertices in the first step. Suppose first that $\Psi_e(G)=1$. Then $|V(G)|=2d$. Taking an arbitrary edge $uv$, we can partition $V(G)$ into $A=N(u)$ and $B=N(v)$, each of size $d$. By triangle-freeness these sets are independent, and $d$-regularity implies that $G$ is the complete bipartite graph with parts $A,B$. This contradicts our no $K_{d,d}$ assumption. Suppose next that $\Psi_e(G)>1$. Consider the position after $\Psi_e(G)-1$ explosion steps. The remaining graph has $2d-1$ vertices. If it has an edge whose explosion would remove fewer that $2d-1$ vertices, CON can choose it and force NON to delete it. By iteratively choosing and deleting such edges, we are left with a graph $H$ in which every edge $uv$ satisfies $|N_H(u) \cup N_H(v)|=2d-1$. An argument similar to the one above shows that $H$ is a complete bipartite graph, this time with one part, say $A$, of size $d$ and the other, $B$, of size $d-1$. Returning to $G$, each $x \in A$ has precisely one neighbor in $V(G)\setminus V(H)$. This neighbor cannot be the same for all $x \in A$, or else a $K_{d,d}$ is formed. Let $xy$ be an edge with $x \in A$ and $y \in V(G)\setminus V(H)$. Let $z\in A$ be a non-neighbor of $y$. CON can choose $xy$ as the first step edge in the game, and exploding it removes all but at most one neighbor of $z$. If $z$ is isolated, the result is $\infty$. If it still has a neighbor $w$, then CON can choose $zw$ at the second step. NON must explode it (to avoid isolating $z$), but this explosion removes at most $d+1$ vertices, which is less than $2d-1$ (as we assume $d>2$). \end{proof} \section{Degree conditions for cooperative coloring} A basic fact on standard graph coloring is that a graph of maximal degree $d$ is $(d+1)$-colorable. Rephrased in our terminology, this says that if $G_1,G_2,\ldots,G_{d+1}$ are identical graphs of maximal degree $d$, then they have a cooperative coloring. Our first observation is that this is no longer true for non-identical graphs. \begin{theorem}\label{dplusone} For every $d \ge 2$, there exists a cooperative coloring system $G_1,G_2,\ldots,G_{d+1}$ with $\Delta(G_i)=d$ for $i=1,\ldots,d+1$, that does not have a cooperative coloring. \end{theorem} \begin{proof} First, we construct an ISR-system $(G,(V_i)_{i=1}^n)$ with $\Delta(G)=d$, $|V_i|=d+1$ for all $i$, having no ISR (as mentioned above, this can be done even with $|V_i|=2d-1$, but for completeness we give the easy construction that we need here). Let $n=4$, and $V_i=U_i \cup \{v_i\}$ where $|U_i|=d$ and $v_i \notin U_i$, $i=1,\ldots,4$. Let $G$ have three connected components: a $K_{d,d}$ with sides $U_1,U_2$, a $K_{d,d}$ with sides $U_3,U_4$, and a $K_{2,2}$ with sides $\{v_1,v_2\},\{v_3,v_4\}$. Clearly, this system has no ISR. From this system, we pass to a cooperative coloring system $\cc(G,(V_i)_{i=1}^4)$ which, as shown at the end of Section~2, has no cooperative coloring. Each of the first $d$ graphs in the system is a disjoint union of $K_{d+1}$'s, and the last graph is $G$, so they all have maximal degree $d$, as required. \end{proof} If $d+1$ graphs of maximal degree $d$ do not suffice for a cooperative coloring, how many of them are needed? More generally, for CLC-systems, how high does the multiplicity need to be (in terms of the maximal degree $d$) in order to guarantee the existence of a cooperative list coloring? We get an upper bound by applying the reduction of CLC-systems to ISR-systems described in Section~2, and invoking Theorems~\ref{penny} and \ref{kdd}. \begin{corollary}\label{2dco} Any CLC-system of multiplicity $2d$ or more, in which the graphs have maximal degree $d$, has a cooperative list coloring. Moreover, for $d>2$ multiplicity $2d-1$ suffices, unless the graphs in the system have between them at least $2d-1$ copies of $K_{d,d}$. \end{corollary} The two parts of the corollary bear a similarity to the known facts about standard (or list) graph coloring: there, $d+1$ colors (or lists of size $d+1$) are needed to color a graph of maximal degree $d$, and Brooks' theorem asserts that one color (or list element) may be saved in the absence of $K_{d+1}$, for $d>2$. But, contrary to this analogy to graph coloring, and unlike the situation for Theorems~\ref{penny} and \ref{kdd} from which it was derived, Corollary~\ref{2dco} is not sharp for general $d$. The reason is that the reduction of CLC-systems to ISR-systems described in Section~2 yields layered ISR-systems. An asymptotic result of Loh and Sudakov~\cite{ls} implies that for such systems $V_i$s of size $(1+o(1))d$ suffice for an ISR. In particular, multiplicity $(1+o(1))d$ in a CLC-system suffices for a cooperative list coloring. However, it is not known whether multiplicity $d+O(1)$ suffices for a cooperative list coloring. In view of Theorem~\ref{dplusone}, $d+1$ does not suffice, but the question for $d+2$ is open. In particular, do every $d+2$ graphs of maximal degree $d$ on the same vertex set have a cooperative coloring? The following theorem shows that no counterexample to the latter can exist, in which $d$ of the graphs are identical (as was the case in the construction of the counterexample for $d+1$ graphs above). \begin{theorem}\label{dthesame} $d+2$ graphs of maximal degree $d$ on the same vertex set have a cooperative coloring, provided that $d$ of the graphs are identical. \end{theorem} The proof of Theorem~\ref{dthesame} requires the following lemma, in which we speak of a \emph{partial} ISR for a system $(G,(V_i)_{i=1}^n)$: this is a choice of independent representatives from some of the $V_i$s, and is expressed as a function $h$ with domain $dom(h) \subseteq [n]$. \begin{lemma}\label{lemma} If $H_1,H_2$ are two graphs on the same vertex set $V$ having both degrees at most $d$, and $(V_i)_{i=1}^n$ is a partition of $V$ into sets of size at least $d$, then there exist a partial ISR $h_1$ for $(H_1,(V_i))$ and a partial ISR $h_2$ for $(H_2,(V_i))$, such that $dom(h_1) \cup dom(h_2)=[n]$. \end{lemma} \begin{proof} We form an ISR-system $(G^*,(V^*_i)_{i=1}^n)$ on a vertex set $V^*$ consisting of two disjoint copies of $V$. The graph $G^*$ is the disjoint union of $H_1$ and $H_2$, placed on the two respective copies of $V$. Each $V^*_i$ is the union of the two respective copies of $V_i$. By Theorem~\ref{penny}, there is an ISR for $(G^*,(V^*_i)_{i=1}^n)$; clearly, such an ISR decomposes into partial ISRs for $H_1$ and $H_2$ as desired. \end{proof} We can now prove Theorem~\ref{dthesame}. By Corollary~\ref{2dco}, we may assume that $d \ge 3$. Say our cooperative coloring system consists of $d$ copies of the same graph $G$, and two additional graphs $G_{d+1},G_{d+2}$, all of maximal degree $d$. Let $V_1,\ldots,V_n,V_{n+1},\ldots,V_r$ be the partition of the vertex set $V$ into the connected components of $G$, enumerated so that $G[V_i]$ is $d$-colorable if and only if $n+1 \le i \le r$. Clearly, $\bigcup_{i=n+1}^rV_i$ can be covered by independent sets from the $d$ copies of $G$. If $n=0$ we are done; if $n>0$ it suffices to find a cooperative coloring of $V':=\bigcup_{i=1}^nV_i$. By Brooks' theorem, each $G[V_i]$ ($1 \le i \le n$) is a $K_{d+1}$. Applying Lemma~\ref{lemma} to the graphs $G_{d+1}[V'],G_{d+2}[V']$, we find independent sets in these two graphs whose union contains a vertex from each $V_i$, $i=1,\ldots,n$. The remaining $d$ vertices in each of these $V_i$s can be covered by independent sets from the $d$ copies of $G$, thus obtaining the desired cooperative coloring. \section{The case $d=2$} The ISR problem for a $2$-regular graph $G$ and $V_i$s of size $3$ is of particular interest. When $G$ is just one cycle, the existence of an ISR is precisely the conjecture of Du, Hsu, and Hwang~\cite{dhh}. That conjecture, in a stronger $3$-colorability version proposed by Erd\H{o}s~\cite{erdos}, became well known and got the name ``the cycle-plus-triangles problem''. It was proved by Fleischner and Stiebitz~\cite{fs} and Sachs~\cite{sachs}. Counterexamples have been found, showing that the result does not extend to all graphs $G$ that consist of several disjoint cycles. But there has not been a good insight as to what features of the decomposition into cycles are needed for a positive answer. We show here, using topological connectivity and Theorems~\ref{connectivityofpaths} and \ref{connectivityofcycles}, that the $\bmod 3$ length of the cycles is crucial. \begin{theorem}\label{mod3isr} Let $\Delta(G)=2$, and assume that at most two connected components of $G$ are cycles of length $1(\bmod 3)$. If $|V_i| \ge 3$ for all $i$, then there exists an ISR. \end{theorem} \begin{proof} By Theorem~\ref{ah}, it suffices to show that for every $I \subseteq [n]$, $\eta(\ci(G) \upharpoonright V_I)$ is at least $|I|$. Let $H_1,\ldots,H_r$ be the connected components of $G[V_I]$, with $n_1,\ldots,n_r$ vertices respectively. Note that $\sum_{j=1}^rn_j=|V_I| \ge 3|I|$. By our assumption on $G$, all but at most two of the $H_j$'s are paths of any length or cycles of length $0$ or $2$ modulo $3$; the exceptional cases are cycles of length $1(\bmod 3)$. Applying Theorems~\ref{connectivityofpaths} and \ref{connectivityofcycles}, we have $\eta_H(\ci(H_j)) \ge \frac{n_j}{3}$ for all $j$ except possibly two $j$'s for which $\eta_H(\ci(H_j))=\frac{n_j-1}{3}$. Lemma~\ref{additive} yields \begin{equation*} \eta_H(\ci(G) \upharpoonright V_I) \ge \lceil \frac{\sum_{j=1}^rn_j-2}{3} \rceil \ge \lceil \frac{3|I|-2}{3} \rceil =|I|. \end{equation*} \end{proof} Theorem~\ref{mod3isr} is sharp: an example with three $4$-cycles and $V_i$s of size $3$ without an ISR is known. In order to show that it is not just $4$-cycles, but cycles of length $1(\bmod 3)$ in general, that hinder ISRs, we prove the following. \begin{theorem}\label{manycycles} For every $\ell \equiv 1(\bmod 3)$, $\ell \ge 4$, there exists a graph, all of whose connected components are cycles of length $\ell$, and a partition of its vertex set into sets of size $3$, for which there is no ISR. Such an example exists with $\frac{\ell}{2}+1$ cycles if $\ell$ is even, and with $\ell+2$ cycles if $\ell$ is odd. \end{theorem} The building block for the necessary construction is presented in the following lemma. \begin{lemma}\label{onecycle} Let $\ell=3r+1$, $r \ge 1$. The vertices of a cycle of length $\ell$ can be partitioned into $r-1$ sets $V_1,\ldots,V_{r-1}$ of size $3$ and $2$ sets $U_0,U_r$ of size $2$ each, so that there is no ISR. \end{lemma} \begin{proof} Let the vertices of the cycle be enumerated in cyclical order as $v_1,v_2,\ldots,v_\ell$. Let \begin{equation*} V_i=\{v_{3i-1},v_{3i+1},v_{3i+3}\},\,\, i=1,\ldots,r-1,\quad U_0=\{v_1,v_3\},\quad U_r=\{v_{\ell-2},v_\ell\}. \end{equation*} \noindent Suppose, for the sake of contradiction, that $A$ is an independent set in the cycle containing an element from each of $U_0,V_1,\ldots,V_{r-1},U_r$. If the $U_0$ element of $A$ is $v_3$, then the $V_1$ element must be $v_6$, the $V_2$ element must be $v_9$, $\ldots$, the $V_{r-1}$ element must be $v_{\ell-1}$, leaving no choice for the $U_r$ element. A similar argument going backwards shows that the $U_r$ element of $A$ cannot be $v_{\ell-2}$. Thus the $U_0$ element must be $v_1$ and the $U_r$ element must be $v_\ell$, but these two are adjacent on the cycle. \end{proof} We give now the construction for Theorem~\ref{manycycles}. For even $\ell$, we take $\frac{\ell}{2}$ cycles of length $\ell$, and partition the vertices of each of them as in the lemma. This gives us a total of $\frac{\ell}{2}(r-1)$ sets of size $3$, and $\ell$ sets of size $2$. We add a new vertex to each of these $\ell$ sets, increasing their size to $3$, and place a new cycle on the new vertices. The way we place that cycle is arbitrary, except that for one of the pairs $U_0,U_r$, the two vertices added to them, denoted $u_0,u_r$, are at distance $2$ on the new cycle. By the lemma, any ISR of this system would have to include, for each of the pairs $U_0,U_r$, one of their two new vertices. This requires an independent set of size $\frac{\ell}{2}$ from the new cycle, but by construction, no such set contains exactly one of $u_0,u_r$. For odd $\ell$, we carry out a similar construction with $\ell$ original cycles of length $\ell$, giving us a total of $\ell(r-1)$ sets of size $3$, and $2\ell$ sets of size $2$. We add a new vertex to each of these $2\ell$ sets, and place two new disjoint cycles on them arbitrarily. The non-existence of an ISR follows from the lemma and the fact that independent sets from the two new (odd) cycles of length $\ell$ can only have total size $\ell-1$. \smallskip We note that Vandenbussche and West~\cite{vw} gave a construction similar to the above, but only for $\ell \equiv 1(\bmod 6)$ - our odd case. This led them to conjecture that if a $2$-regular graph $G$ on $V$ has girth at least $\sqrt{|V|}$, and $V$ is partitioned into sets of size $3$, then there is an ISR (with the exception of a particular $12$-vertex example). Our construction above for even $\ell$ has girth $\ell$ and $|V|=\frac{\ell^2+2\ell}{2}$, so it disproves their conjecture by a factor of $\sqrt{2}$. The conjecture may still be true up to a constant factor. Theorem~\ref{manycycles} also serves to show that the condition $d>2$ in Theorem~\ref{kdd} is necessary. Turning now to cooperative coloring in the case $d=2$, we have the following corollary of Theorem~\ref{mod3isr}. \begin{corollary}\label{mod3co} A CLC-system of multiplicity $3$, in which all graphs have degrees at most $2$, and the total number of components which are cycles of length $1(\bmod 3)$ is at most $2$, has a cooperative list coloring. \end{corollary} Theorem~\ref{manycycles} also has a cooperative list coloring counterpart. \begin{theorem}\label{manycyclesco} For every $\ell \equiv 1(\bmod 3)$, $\ell \ge 4$, there exists a CLC-system of multiplicity $3$, in which all graphs are cycles of length $\ell$, that does not have a cooperative list coloring. \end{theorem} \begin{proof} Note that we cannot just apply to the ISR-system constructed in Theorem~\ref{manycycles} the transformation to a cooperative coloring system described in Section~2 (because then only one of the graphs in the system would have cycles of length $\ell$, the others would have $3$-cliques). We do start with the ISR-system $(G, (V_i)_{i=1}^n)$ produced in Theorem~\ref{manycycles}, but proceed differently. We augment each $V_i$ by adding $\ell-2$ new vertices, obtaining a set of size $\ell+1$ written as $U_i=\{v^1_i,v^2_i,v^3_i,\ldots,v^{\ell+1}_i\}$, where the first $3$ elements are those of $V_i$. Thus the vertex set of the CLC-system will be $U=\bigcup_{i=1}^nU_i$, of size $n(\ell+1)$. The graphs in the system are the cycles of $G$ and $3n$ new cycles: for each $i=1,\ldots,n$ we introduce the $3$ cycles \begin{equation*} C^1_i:=v^1_i,v^2_i,v^4_i,\ldots,v^{\ell+1}_i,\quad C^2_i:=v^2_i,v^3_i,v^4_i,\ldots,v^{\ell+1}_i, \quad C^3_i:=v^3_i,v^1_i,v^4_i,\ldots,v^{\ell+1}_i. \end{equation*} \noindent Clearly, the resulting CLC-system has multiplicity $3$. Assume, for the sake of contradiction, that it has a cooperative list coloring. Because the original $G$ has no ISR, the independent sets coming from the original cycles leave some $U_i$ untouched. This $U_i$ needs to be covered by independent sets $A_1$ from $C^1_i$, $A_2$ from $C^2_i$, $A_3$ from $C^3_i$. There are only two ways in which $v^1_i,v^2_i,v^3_i$ can all be covered: either $v^1_i \in A_1, v^2_i \in A_2, v^3_i \in A_3$, or $v^1_i \in A_3, v^2_i \in A_1, v^3_i \in A_2$. In the former case, none of the independent sets can contain $v^{\ell+1}_i$; in the latter case, the contradiction is obtained for $v^4_i$. \end{proof} We remark that a CLC-system in which all graphs are $4$-cycles may be interpreted as a CNF formula, and in fact the $\ell=4$ case of Theorem~\ref{manycyclesco} is equivalent to a construction of an unsatisfiable (3,B2)-SAT formula given in~\cite{bks}. We do not know if Theorem~\ref{manycyclesco} can be strengthened to assert the existence of a cooperative coloring system with these properties, i.e., three graphs on the same vertex set, each of them a disjoint union of $\ell$-cycles, having no cooperative coloring. This question remains open, even for $\ell=4$. There is, however, an important special case of cooperative coloring systems, in which a cooperative coloring is guaranteed regardless of the $\bmod 3$ length of the cycles. Namely, when each of the three graphs is a cycle on the entire vertex set. \begin{theorem}\label{threecycles} Three cycles on the same vertex set possess a cooperative coloring. \end{theorem} \begin{proof} Let $G_1,G_2,G_3$ be a system of three cycles on the same vertex set $V$. Choose any vertex $v$, and take it into the independent set chosen from $G_1$. Completing this choice to a cooperative coloring means finding an ISR in the ISR-system $\ck$ obtained from $\cj(G_1,G_2,G_3)$ by removing the set $V_v$, and removing from the $G_1$-copy of $V$ the two vertices (that we shall name below $u$ and $w$) adjacent to $v$ in $G_1$. We shall prove that $\ck$ satisfies the conditions of Theorem \ref{ah}. Write $V'_y=V_y$ for $y \in V\setminus \{v,u,w\}$, and let $V'_u, V'_w$ be obtained from $V_u, V_w$, by removing the $G_1$-copies of $u,~w$, respectively. Let $H$ be the underlying graph of $\ck$. Let $X$ be a subset of $V \setminus \{v\}$. Because $V_v$ was removed, the three graphs induced on the three copies of $X$ in $H$ have only paths as their connected components. By Theorem~\ref{connectivityofpaths}, $\eta_H$ of each path is at least a third of its number of vertices. The total number of vertices in $\bigcup_{x \in X}V'_x$ is at least $3|X|-2$. Thus we get by Lemma~\ref{additive} \begin{equation*} \eta(\ci(H) \upharpoonright \bigcup_{x \in X}V'_x) \ge \lceil \frac{3|X|-2}{3}\rceil = |X|, \end{equation*} \noindent as required in order to apply Theorem~\ref{ah}. \end{proof} \section{Open problems} Let us summarize some of the main open problems concerning cooperative colorings and ISRs (some of them have already been mentioned above). \begin{enumerate} \item A central problem on cooperative colorings is whether there exists some constant $c$ such that $d+c$ graphs of maximum degree $d$ always have a cooperative coloring. At the moment, even the case $c=2$ is open. \item The list version of the above, where $d+c$ is the multiplicity of the CLC-system. \item Understand what makes layered ISR systems special, and why they behave better than ordinary systems. If the layers are known to be full, or alternatively to be induced from the same graph, does the behavior become even better? \item A more general notion than layered ISR systems, considered in \cite{ls}, is that of locally sparse systems, in which every vertex is connected to $o(d)$ vertices in each $V_i$. Is this the property that is really relevant? \item In all examples known in which $|V_i|=2d-1$ and yet there are no ISRs, not only is there a $K_{d,d}$-component in the graph, but there is such a component which is contained in the union of two $V_j$s. It would be interesting to strengthen Theorem~\ref{kdd} accordingly. \item Do three graphs on the same vertex set, each of them a disjoint union of $\ell$-cycles, always have a cooperative coloring? The first interesting case is $\ell=4$. \item A small challenge - find a combinatorial proof of Theorem \ref{threecycles}. \end{enumerate} \begin{thebibliography}{99} \bibitem{adba} M. Adamaszek and J. A. Barmak, On a lower bound for the connectivity of the independence complex of a graph, \emph{Discrete Math.} {\bf 311} (2011), 2566--2569. \bibitem{aab} R. Aharoni, N. Alon and E. Berger, Eigenvalues of $K_{1,k}$-free graphs and the connectivity of their independence complexes, {\em submitted}. \bibitem{ABM} R. Aharoni, E. Berger and R. Meshulam, Eigenvalues and homology of flag complexes and vector representations of graphs, {\em Geom. Funct. Anal.} {\bf 15} (2005), 555--566. \bibitem{abz} R. Aharoni, E. Berger and R. Ziv, Independent systems of representatives in weighted graphs, \emph{Combinatorica} {\bf 27} (2007), 253--267. \bibitem{ah} R. Aharoni and P. Haxell, Hall's theorem for hypergraphs, \emph{J. of Graph Theory} {\bf 35} (2000), 83--88. \bibitem{bks} P. Berman, M. Karpinski and A. D. Scott, Approximation hardness of short symmetric instances of MAX-3SAT, \emph{Elec. Coll. on Comp. Compl.} (2003), ECCC TR03-049. \bibitem{bjorner} A. Bj\"orner, Topological methods, in \emph{Handbook of combinatorics, Vol. 2} (eds. R.~L.~Graham, M.~Gr\"otschel and L.~Lov\'asz), North-Holland, Amsterdam, 1995, 1819--1872. \bibitem{bh} T. Bohman and R. Holzman, On a list coloring conjecture of Reed, \emph{J. Graph Theory} {\bf 41} (2002), 106--109. \bibitem{dhh} D.-Z. Du, D. F. Hsu and F. K. Hwang, The Hamiltonian property of consecutive-$d$ digraphs, in \emph{Graph-theoretic models in computer science, II(Las Cruces, NM, 1988-1990), Mathematical and Computer Modelling} {\bf 17} (1993), 61--63. \bibitem{erdos} P. Erd\H{o}s, On some of my favorite problems in graph theory and block design, in \emph{Graphs, designs and combinatorial geometries (Catania, 1989), Le Matematiche} {\bf 45} (1990), 61--73. \bibitem{fs} H. Fleischner and M. Stiebitz, A solution to a colouring problem of P. Erd\H{o}s, \emph{Discrete Math.} {\bf 101} (1992), 39--48. \bibitem{penny95} P. E. Haxell, A condition for matchability in hypergraphs, \emph{Graphs and Combinatorics} {\bf 11} (1995), 245--248. \bibitem{penny01} P. E. Haxell, A note on vertex list coloring, \emph{Combin. Probab. Comput.} {\bf 10} (2001), 345--347. \bibitem{jin} G. P. Jin, Complete subgraphs of $r$-partite graphs, \emph{Combin. Probab. Comput.} {\bf 1} (1992), 241--250. \bibitem{ls} P.-S. Loh and B. Sudakov, Independent transversals in locally sparse graphs, \emph{J. Combin. Theory Ser. B} {\bf 97} (2007), 904--918. \bibitem{mesh01} R. Meshulam, The clique complex and hypergraph matching, \emph{Combinatorica} {\bf 21} (2001), 89--94. \bibitem{mesh03} R. Meshulam, Domination numbers and homology, \emph{J. Combin. Theory Ser. A} {\bf 102} (2003), 321--330. \bibitem{reed} B. Reed, The list colouring constants, \emph{J. Graph Theory} {\bf 31} (1999), 149--153. \bibitem{rs} B. Reed and B. Sudakov, Asymptotically the list colouring constants are $1$, \emph{J. Combin. Theory Ser. B} {\bf 86} (2002), 27--37. \bibitem{sachs} H. Sachs, Elementary proof of the cycle-plus-triangles theorem, in \emph{Combinatorics, Paul Erd\H{o}s is eighty, Vol. 1, Bolyai Soc. Math. Stud.} (1993), 347--359. \bibitem{st} T. Szab\'o and G. Tardos, Extremal problems for transversals in graphs with bounded degree, \emph{Combinatorica} {\bf 26} (2006), 333--351. \bibitem{vw} J. Vandenbussche and D. B. West, Independence number of $2$-factor-plus-triangles graphs, \emph{Electron. J. Combin.} {\bf 16} (2009), \#R27. \bibitem{yuster} R. Yuster, Independent transversals in $r$-partite graphs, \emph{Discrete Math.} {\bf 176} (1997), 255--261. \end{thebibliography} \end{document}