%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%            Packing and Covering Triangles in Tripartite Graphs
% 
%                    P.E. Haxell and Y. Kohayakawa
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%                    Last updated on 19 December 1995
% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\magnification=\magstephalf
\input amstex
\documentstyle{amsppt}
\refstyle{C}
%
% refdef
%
\newcount\refno\refno=1
\def\referencelabel{\number\refno} 
\def\newrefno{\advance\refno by1}
%
\edef\refnoFuSurvey
{\referencelabel}\newrefno
\def\refFuSurvey{{\bf[\refnoFuSurvey]}}
\edef\refnoHaxellRy
{\referencelabel}\newrefno
\def\refHaxellRy{{\bf[\refnoHaxellRy]}}
\edef\refnoKri
{\referencelabel}\newrefno
\def\refKri{{\bf[\refnoKri]}}
\edef\refnoTuConj
{\referencelabel}\newrefno
\def\refTuConj{{\bf[\refnoTuConj]}}
\edef\refnoTuB
{\referencelabel}\newrefno
\def\refTuB{{\bf[\refnoTuB]}}
\edef\refnoTuC
{\referencelabel}\newrefno
\def\refTuC{{\bf[\refnoTuC]}}
%
% Journals
%
\def\BLMS{Bull. London Math. Soc.}
\def\BAMS{Bull. Amer. Math. Soc.}
\def\JAMS{J. Amer. Math. Soc.}
\def\JLMS{J. London Math. Soc.}
\def\PLMS{Proc. London Math. Soc.}
\def\JCT{J. Combinatorial Theory}
\def\JCTA{J. Combinatorial Theory~(A)}
\def\JCTB{J. Combinatorial Theory~(B)}
\def\JGT{J. Graph Theory}
\def\Comb{Combinatorica}
\def\CPC{Combinatorics, Probability and Computing}
\def\AMASH{Acta Math. Acad. Sci. Hungar.}
\def\SSMH{Studia Sci. Math. Hung.}
\def\EJC{Europ. J. Combinatorics}
\def\GC{Graphs and Combinatorics}
\def\IJM{Israel J. Math.}
\def\DM{Discrete Math.}
\def\ADM{Ann. Discrete Math.}
\def\TAMS{Trans. Amer. Math. Soc.}
\def\PAMS{Proc. Amer. Math. Soc.}
\def\PMH{Periodica Math. Hungar.}
\def\PCPS{Proc. Cambridge Phil. Soc.}
\def\MPCPS{Math. Proc. Cambridge Phil. Soc.}
\def\RSA{Random Structures and Algorithms}
% Authors
\def\Aj{Ajtai, M.}
\def\Al{Alon, N.}
\def\Be{Beck, J.}
\def\BB{Bollob\'as, B.}
\def\Chung{Chung, F.R.K.}
\def\Er{Erd\H os, P.}
\def\Fr{Frankl, P.}
\def\Fu{F\"uredi, Z.}
\def\Gra{Graham, R.L.}
\def\Ka{Katona, G.O.H.}
\def\Kl{Kleitman, D.J.}
\def\Ko{Koml\'os, J.}
\def\Lo{Lov\'asz, L.}
\def\Ne{Ne\v set\v ril, J.}
\def\Po{P\'osa, L.}
\def\Ro{R\"odl, V.}
\def\Sey{Seymour, P.}
\def\Sh{Shearer, J.B.}
\def\Si{Simonovits, M.}
\def\So{S\'os, V.T.}
\def\Sp{Spencer, J.H.}
\def\Sz{Szemer\'edi, E.}
\def\Tur{Tur\'an, P.}
\def\Tutte{Tutte, W.T.}
\def\Tu{Tuza, Zs.}
%
% macros
%
\hoffset=1.5truecm
\overfullrule=0pt
\def\({\left(}
\def\){\right)}  
\def\[{\left[}
\def\]{\right]}
\def\e{{\text{\rm e}}}
\let\epsilon=\varepsilon
\let\phi=\varphi
\def\deffont{\it}
%
\newcount\eqnocounter
\eqnocounter=0
\def\slabel#1{\global\advance\eqnocounter by1%
  \global\expandafter\edef\csname eqno#1\endcsname{(\number\eqnocounter)}%
  \eqno({\number\eqnocounter})}
\def\alabel#1{\global\advance\eqnocounter by1%
  \global\expandafter\edef\csname eqno#1\endcsname{(\number\eqnocounter)}%
  ({\number\eqnocounter})}
%
\def\endclaim{\egroup\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty20\smallskip\fi}
\long\def\claim{\smallbreak\noindent  
  {\it Claim.\enspace}\ignorespaces\bgroup\sl}
  \def\endassertion{\egroup\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty20\smallskip\fi}
\def\endassertionsquare{{\unskip\nobreak\hfil\penalty50
  \hskip2em\hbox{}\nobreak\hfil\square
    \parfillskip0pt\finalhyphendemerits=0\par}%
    \egroup\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty20\smallskip\fi}
\long\def\assertion(#1){\smallbreak\noindent 
  {\rm(}{#1}{\rm)}\enspace\ignorespaces\bgroup\sl}
\def\endcase{\par\ifdim\lastskip<\smallskipamount
  \removelastskip\penalty3000\smallskip\fi}
\def\case#1.{\smallbreak\noindent 
  {\sl Case\/} #1.\enspace\ignorespaces}
\def\casenodot#1 {\smallbreak\noindent 
  {\sl Case\/} #1\enspace\ignorespaces}
\def\endcasebody{\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty-20\smallskip\fi}
\outer\def\endcasebodysquare{{\unskip\nobreak\hfil\penalty50
         \hskip2em\hbox{}\nobreak\hfil\square
         \parfillskip0pt\finalhyphendemerits=0\par}% TeXbook, p 106.
  {\ifdim\lastskip<\smallskipamount\removelastskip\penalty-10\smallskip\fi}}
\def\casebody{\noindent\ignorespaces}
\let\proofofassertion=\casebody
\let\endproofofassertion=\endcasebody
\let\endproofofassertionsquare=\endcasebodysquare
\def\proofoftheclaim{\proofofassertion{\it Proof of the Claim\/}.\enspace}
\let\endproofoftheclaim=\endproofofassertion
%
%
\def\arrow{\to}
%
% new macros
%
%\def\:{{:}\;}
\let\:=\colon
\def\cF{{\Cal F}}
\def\cB{{\Cal B}}
\def\cE{{\Cal E}}
\def\cS{{\Cal S}}
\def\cT{{\Cal T}}
\def\cH{{\Cal H}}
\def\bV{{\bar V}}
\def\bE{{\bar E}}
\def\yk{{\it yk\/}}
%
% statems
%
\newcount\statemno\statemno=1
\def\newstatemno{\advance\statemno by1}
\def\statementlabel{\number\statemno} %new command
%
% \S1
%
\edef\LemmaA
{\statementlabel}\newstatemno
\edef\LemmaB
{\statementlabel}\newstatemno
\edef\LemmaC
{\statementlabel}\newstatemno
%
% \S2
%
\edef\ThmA
{\statementlabel}\newstatemno
%
% fstpg
%
\topmatter
\title
Packing and Covering Triangles in\\ 
Tripartite Graphs
\endtitle
\rightheadtext{PACKING AND COVERING TRIANGLES IN GRAPHS}
\author
P.E.~Haxell and Y.~Kohayakawa 
\endauthor
\address
\noindent
Department of Combinatorics and Optimisation, 
University of Waterloo, Waterloo, Ontario, 
Canada N2L 3G1
\endaddress
\email{\tt<pehaxell\@math.uwaterloo.ca>}
\endemail
\address
\noindent
Instituto de Matem\'atica e Estat\'\i stica, 
Universidade de S\~ao Paulo, Cidade Universit\'aria, 
Rua do Mat\~ao~1010, 05508--900 S\~ao Paulo, SP, 
Brazil
\endaddress
\email{\tt<yoshi\@ime.usp.br>}
\endemail
\keywords Packing, covering, triangles, tripartite graphs, Tuza's conjecture 
\endkeywords
\subjclass Primary 05C70, % Factorization, matching, covering and packing
  05C35; % Extremal problems
  Secondary 05D15 % Transversal (matching) theory
\endsubjclass
\thanks
The first author was partially supported by NSERC.  The second author was
partially supported by CNPq (Proc.~300334/93--1 and ProTeM-CC-II Project
ProComb).
\endthanks
\abstract 
It is shown that if~$G$ is a tripartite graph such that the maximum
size of a set of pairwise edge-disjoint triangles is~$\nu(G)$, then
there is a set~$C$ of edges of~$G$ of size at most~$(2-\epsilon)\nu(G)$
such that $E(T)\cap C\neq\emptyset$ for every triangle~$T$ of~$G$, where 
$\epsilon>0.044$.  This improves the previous bound of~$(7/3)\nu(G)$ due to
Tuza~{\refTuC}. 
\endabstract
\endtopmatter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\document 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% intro
%
\head\S0. Introduction
\endhead

In this note we are concerned with a packing and covering problem for
triangles in graphs.  Let a graph~$G$ be given.  We say that a family~$\cF$ of
triangles in~$G$ is {\it independent\/} if the elements of~$\cF$ are pairwise
edge-disjoint.  Moreover, we say that a set~$C\subset E(G)$ of edges of~$G$ is
a {\it transversal of the set of triangles of~$G$\/}, or simply a {\it
  transversal\/} for~$G$, if every triangle of~$G$ contains at least one
element of~$C$.  We denote by~$\nu(G)$ the maximum cardinality of an
independent family of triangles in~$G$, and by~$\tau(G)$ the minimum
cardinality of a transversal for~$G$.  It is clear that for every graph~$G$ we
have~$\nu(G)\leq\tau(G)\leq 3\nu(G)$.  The graphs~$G=K^4$ and~$K^5$ show that
we may have~$\tau(G)$ as large as~$2\nu(G)$.  In this note, we are concerned
with an elegant conjecture of Tuza, first raised fifteen years
ago~{\refTuConj}, which 
states that~$\tau(G)\leq2\nu(G)$ for every graph~$G$.

Some partial results on this conjecture have been obtained for certain special
classes of graphs. In~{\refTuC}, Tuza shows that the conjecture is true for
planar graphs, chordal graphs, and graphs with~$n$ vertices and at
least~$7n^2/16$ edges.  More recently, Krivelevich~{\refKri} has shown that
graphs~$G$ without homeomorphic copies of~$K^{3,3}$ satisfy the conjecture,
improving on Tuza's result that the conjecture holds for planar graphs.  Two
fractional versions of the conjecture are considered by Krivelevich~{\refKri}
as well.  Tuza~{\refTuC} also shows that for tripartite graphs~$G$ one
has~$\tau(G)\leq7\nu(G)/3$. In this note we prove that~$\tau(G)\leq
(2-\epsilon)\nu(G)$ for tripartite graphs~$G$, where~$\epsilon>0.044$.  We
give a short, self-contained proof of the inequality~$\tau(G)\leq2\nu(G)$ (see
Lemma~{\LemmaA}); as we shall see, the difficulty will lie in getting
the~$\epsilon$ improvement.  It is interesting to note that it has not even 
been proved that there is a constant $c<3$ such that~$\tau(G)<c\nu(G)$ for
{\it every\/} graph~$G$.

Our result is also a special case of a conjecture of Ryser on packing and
covering in tripartite hypergraphs.  A tripartite hypergraph~$\cH$ consists of
three disjoint sets of vertices~$X_1$, $X_2$, and~$X_3$, and a set~$\cE$ of
hyperedges~$E$, where each hyperedge is a set of three vertices, one from each
$X_i$.  Ryser conjectured that~$\tau(\cH)\leq2\nu(\cH)$ for every
tripartite hypergraph~$\cH$, where here~$\nu(\cH)$ denotes the maximum size of
a set of pairwise disjoint hyperedges of~$\cH$, and~$\tau(\cH)$ is the minimum
size of a set of vertices~$C$ such that~$E\cap C\neq\emptyset$ for
all~$E\in\cE$. The best upper bound for this problem that is currently
known~{\refHaxellRy} is~$\tau(\cH)\leq5\nu(\cH)/2$. For more details on
Ryser's conjecture, see Conjecture~4.29 in F\"uredi~{\refFuSurvey}, and
Tuza~{\refTuB}.  Note that if~$G$ is a tripartite graph then its edge set can
be partitioned into~$3$ classes such that every triangle in~$G$ contains
exactly one edge from each class.  Therefore~$\cT(G)$, the set of triangles in
the graph~$G$, corresponds in an obvious way to the set of hyperedges of a
tripartite hypergraph~$\cH=\cH(G)$, and in our notation~$\tau(G)=\tau(\cH)$
and~$\nu(G)=\nu(\cH)$.  Thus our main result of this note shows that Ryser's
conjecture is true for hypergraphs that are derived from tripartite graphs in
this way.

In~\S1 of this note we give two lemmas needed in the proof of our main result,
Theorem~{\ThmA}. In~\S2 we give the proof of Theorem~{\ThmA}, and also give
examples of tripartite graphs~$G$ with~$\tau(G)\geq5\nu(G)/4$.

\head\S1. Two Lemmas
\endhead

We begin with some definitions and notation.  Let~$G$ be a tripartite graph
with vertex sets~$V_1$, $V_2$, and~$V_3$, and denote by~$E_\sigma$ the set of
edges with one endpoint in~$V_{\sigma+1}$ and the other in~$V_{\sigma+2}$
(here addition is taken modulo 3).  We sometimes say that the vertices
in~$V_\sigma$ and the edges in~$E_\sigma$ are coloured with colour~$\sigma$.
For a path, triangle or set of triangles~$S$ in~$G$, we shall write~$E(S)$ for
the set of all the edges appearing in~$S$, and~$E_\sigma(S)$ for the subset
of~$E(S)$ consisting of the edges in~$E_\sigma$.  In the sequel, if the
vertices~$a$, $b$, and~$c$ induce a triangle~$T=G[\{a,b,c\}]$ in a graph~$G$,
we shall write~$abc$ for this triangle~$T$.  Recall that we denote the family
of triangles of a graph~$G$ by~$\cT(G)$.

\proclaim{Lemma~{\LemmaA}} Let~$\sigma\in\{1,2,3\}$ be fixed, and let~$\cB$ be an
independent set of triangles in~$G$.  Then one of the following assertions
holds.
\roster
\item"(1.1)" There exists an independent set of triangles~$\cB'$ in~$G$
  with~$|\cB'|=|\cB|+1$ such that~$E_{\sigma'}(\cB)\subset E_{\sigma'}(\cB')$
  for both~$\sigma'\neq\sigma$.
\item"(1.2)" We have~$\tau(G)\leq2|\cB|$.
\endroster
\endproclaim
\demo{Proof}
We shall describe how to construct either~$\cB'$ or a transversal~$C$ for~$G$
with~$|C|\leq2|\cB|$.  Observe that we may clearly assume that~$\cB$ is a
maximal independent family of triangles.  In other words, we may assume that
every triangle in~$G$ contains at least one edge of~$E(\cB)$.

For each vertex~$v\in V_\sigma$, let~$\cB_v$ denote the subset of~$\cB$
consisting of triangles containing~$v$.  We define for each~$v\in V_\sigma$ a
bipartite graph~$H_v$ with vertex set~$V_{\sigma+1}\cup V_{\sigma+2}$ as
follows. We let~$xy$ be an edge of~$H_v$ if~$vxy$ is a triangle in~$G$
and~$xy$ is not an edge of~$T$ for any~$T\in\cB\setminus\cB_v$.  We denote
by~$\nu(H_v)$ the maximum size of a matching in~$H_v$.  Note that~$\cB_v$
corresponds to a matching in~$H_v$, which we shall denote by~$M_v$.  Note also
that since~$\cB$ is maximal, we have that~$M_v$ is a maximal matching, {\it
  i.e.\/}, every edge of~$H_v$ not in~$M_v$ is adjacent to an edge of~$M_v$.

\case1. For some~$v\in V_\sigma$, we have~$|M_v|<\nu(H_v)$. 
\endcase
\casebody
In this case, pick an augmenting path $P=x_1y_1x_2y_2\dots x_ky_k$
in~$H_v$, so that~$x_jy_j\notin M_v$ ($1\leq j\leq k$), $y_jx_{j+1}\in M_v$
($1\leq j<k$), and neither~$x_1$ nor~$y_k$ is covered by~$M_v$.  Then the set
of triangles 
$$
\cB'=\Big(\cB\setminus\{vyx\: yx\in E(P)\cap M_v\}\Big)
             \cup\{vxy\:xy\in E(P)\setminus M_v\}
$$
is such that~$|\cB'|=|\cB|+1$.  We now check that the set~$\cB'$ is
independent.  It is clear that those elements of~$\cB'$ containing~$v$ are
independent, as~$(E(P)\setminus M_v)\cup(M_v\setminus E(P))$ is a matching
in~$H_v$. 
Also, if~$T\in\cB'$ does not contain~$v$ then it can intersect a triangle
containing~$v$ only in the edge of colour~$\sigma$.  But by construction, no  
edge of colour~$\sigma$ of any triangle in~$\cB\setminus\cB_v$ appears
in~$H_v$.  Finally we note that~$E_{\sigma+1}(\cB\setminus\cB')\cup
E_{\sigma+2}(\cB\setminus\cB')=\{vu\:u\in V(P)\setminus\{x_1,y_k\}\}\subset
E_{\sigma+1}(\cB')\cup E_{\sigma+2}(\cB')$.  Therefore $\cB'$ satisfies the
conditions of (1.1), and so this case is finished.
\endcasebody 

\case2. For all~$v\in V_\sigma$, we have~$|M_v|=\nu(H_v)$. 
\endcase
\casebody
In this case we describe a transversal~$C$ of $\cT(G)$.  For each~$v\in
V_\sigma$ let~$C_v$ denote a vertex-cover of the edges of~$H_v$ of minimum
size, so~$|C_v|=\nu(H_v)$ by the K\"onig--Egerv\'ary theorem.  We let
$$
C=E_\sigma(\cB)\cup\bigcup_{v\in V_{\sigma}}\{vz\:z\in C_v\}.
$$
Then~$C$ is a transversal, since if~$T\in\cT(G)$ is such that~$E(T)\cap
E_\sigma(\cB)=\emptyset$, then~$T$ is represented as an edge~$e$ of~$H_v$ 
where~$v$ is the vertex of~$T$ of colour~$\sigma$, and so~$vz\in
E(T)\cap C$ where~$z\in C_v$ is a vertex covering~$e$ in~$H_v$. To
estimate~$|C|$, simply notice that~$\sum_{v\in V_\sigma}|C_v|=\sum_{v\in  
V_\sigma}\nu(H_v)=|\cB|$.  Therefore~$|C|=2|\cB|$ and hence~(1.2) is proved.   
\qed%\endcasebody
\enddemo

Note that Lemma~{\LemmaA} immediately implies that~$\tau(G)\leq2\nu(G)$ for
any tripartite graph~$G$.  Our aim now is to improve on Lemma~{\LemmaA} taking
into account certain special edges present in the family~$\cB$.

An edge~$e\in E(\cB)$ appearing in an independent set of triangles~$\cB$ is
said to be {\it essential\/} if there exists a triangle~$T$ of~$G$ such
that~$E(T)\cap E(\cB)=\{e\}$, and we say that such a triangle~$T$ is {\it
  associated with\/}~$e$.  We denote by~$\bE_\sigma(\cB)$ the set of edges in
$E_\sigma$ that are essential in~$\cB$, and we
let~$\nu_\sigma(\cB)=|\bE_{\sigma}(\cB)|$.  A refinement of Lemma~{\LemmaA} is
as follows. 

\proclaim{Lemma~{\LemmaB}} Let~$\sigma\in\{1,2,3\}$ be fixed, and let~$\cB$ be
an independent set of triangles in~$G$.  Then one of the following assertions 
holds. 
\roster
\item"(2.1)" There exists an independent set of triangles~$\cB'$ in~$G$
  with~$|\cB'|=|\cB|+1$ such that for both~$\sigma'\neq\sigma$,
  we have $|E_{\sigma'}(\cB)\cap E_{\sigma'}(\cB')|\geq|\cB|-1$. 
\item"(2.2)" We have~$\tau(G)\leq2|\cB|-\nu_{\sigma}(\cB)$.  
\endroster
\endproclaim
\demo{Proof} For each~$v\in V_\sigma$ we define~$\cB_v$, $H_v$, and~$M_v$ as
in the proof of Lemma~{\LemmaA}, and we assume as before that~$\cB$ is
maximal, and hence that each~$M_v$ is a maximal matching in~$H_v$.

A vertex $x\in H_v$ is called {\it $v$-essential of type 1\/} if there is an
alternating path $P(x)=y_0x_1y_1x_2y_2\dots x_k$ with~$x_1=x$, $k\geq 1$,
$x_jy_j\notin M_v$ ($1\leq j\leq k$) and $y_jx_{j+1}\in M_v$ ($0\leq j<k$),
and~$vx_k$ is an essential edge for~$\cB$.  The vertex $x$ is said to be
$v$-essential of {\it type 2\/} if the path~$P(x)$ as above exists, $k\geq 2$,
and~$y_{k-1}x_k$ rather than~$vx_k$ is an essential edge. A {\it
  $v$-essential\/} vertex is one that is $v$-essential of type~1 or type~2.
Note that if~$x$ is $v$-essential then~$x_i$ is also $v$-essential for
$i=1,\dots,k-1$, and also so is~$x_k$ if~$x$ is of type~1. We denote
by~$\bV(H_v)$ the set of $v$-essential vertices of~$H_v$.

To prove Lemma~{\LemmaB}, we assume that there does not exist an independent
set~$\cB'$ of triangles as in~{\rm(2.1)} of our lemma, and prove the
following assertion.

\assertion(*) For every vertex~$v\in V_\sigma$, we have 
\roster
\item"({\it i\/})" each edge of~$M_v$ is incident with at most one
  $v$-essential vertex, 
\item"({\it ii\/})" the set~$C=E_\sigma(\cB)\cup C_2\cup C_3$ is a transversal
  for~$G$, where 
  $$\eqalign{
    C_2&=\{vx\:x\in\bV(H_v)\},\cr
    C_3&=\{vy\:y\in V_{\sigma+1}\text{ and }wy\in M_v
                 \text{ for some $w$}\cr 
       &\qquad\qquad\qquad\qquad\qquad
                 \text{ such that }wy\notin\bE_\sigma(\cB)
                 \text{, and $w$, $y\notin\bV(H_v)$}\}.\cr}
  $$
  Moreover, $|C|\leq2|\cB|-\nu_\sigma(\cB)$. 
\endroster
\endassertion

We now proceed to prove assertion~(*).  Let~$v\in V_\sigma$ be fixed. 

\demo{Proof of~{\rm({\it i\/})}} Suppose on the contrary that~$xz\in M_v$ is
such that both~$x$ and~$z$ are $v$-essential.  Let~$P(x)=zxy_1x_2\dots x_k$
and $P(z)=xzw_1z_2\dots z_l$ be the alternating paths associated with~$x$
and~$z$.  We may assume that we have chosen the triple~$(xz,P(x),P(z))$
so as to minimise the sum~$k+l$.  We shall need the following
technical lemma, the proof of which is postponed to the end of this section. 

\proclaim {Lemma~{\LemmaC}} The paths~$P(x)$ and~$P(z)$ are
vertex-disjoint, except for~$x$ and~$z$. 
\endproclaim

Assuming the result of Lemma {\LemmaC}, we now proceed to derive a
contradiction to the assumption that $\cB'$ as in~(1.1) of the lemma
does not exist. We first note that the following statement holds.

\assertion(**) The family
$$
\eqalign{\cB''=\Big(\cB&\setminus\{vab\:ab\in E(P(x)\cup
P(z))\cap M_v\}\Big)\cr 
            &\qquad\qquad\cup\{vab\:ab\in E(P(x)\cup P(z))\setminus
                  M_v\}}
$$ 
is an independent set of triangles of size $|\cB|-1$, and 
$$
E_{\sigma+1}(\cB\setminus\cB'')\cup
E_{\sigma+2}(\cB\setminus\cB'')\subset
E_{\sigma+1}(\cB'')\cup E_{\sigma+2}(\cB'')\cup\{vx_k, vz_l\}.
$$
\endassertion

\proofofassertion
Indeed, since $\big[(E(P(x))\cup E(P(z)))\setminus
M_v\big]\cup\big[M_v\setminus(E(P(x))\cup E(P(z)))\big]$ is a matching in 
$H_v$, the set $\cB''_v$ of triangles in $\cB''$ containing $v$ are
all edge-disjoint. Also, a triangle in $\cB''_v$ can intersect a
triangle in $\cB''\setminus\cB''_v=\cB\setminus\cB_v$ only in the edge
of colour $\sigma$, but this is not possible since the edges in
$E_{\sigma}(\cB\setminus\cB_v)$ are not present in~$H_v$ by
construction. Therefore $\cB''$ is independent, and also clearly has
size $|\cB|-1$. The edge condition in~(**) follows immediately from
the definition.  
\endproofofassertion

Now to obtain the desired contradiction, we shall show that it is
possible to add two more triangles to $\cB''$ to form an independent
set of triangles satisfying~(2.1) of the lemma. Note that the edge
condition in (2.1) will then follow directly from the edge condition
in~(**). We shall consider three different cases, according to the type 
of the vertices $x$ and $z$.  

\case1.  The vertices~$x$ and~$z$ are both of type~1. 
\endcase
\casebody
Let~$vx_kc$ and~$vz_ld$ be triangles associated with the $v$-essential
edges~$vx_k$ and~$vz_l$ respectively.  Let
$$
\cB'=\cB''\cup\{vx_kc,vz_ld\}.
$$
%
Note that~$vx_kc$ and~$vz_ld$ are also edge-disjoint from each other
and the rest of~$\cB'_v=\{vxy\in\cB'\}$, since~$c$ and~$d$ are not
incident with any edge 
of~$M_v$ as~$vx_k$ and~$vz_l$ are essential for~$\cB$, and hence in particular
are not equal to any vertex of~$P(x)\cup P(z)$.  Also~$c\neq d$ since they are
in different vertex classes.  Therefore~$\cB'$ is a set of pairwise
edge-disjoint triangles satisfying~(2.1).
\endcasebody

\case2. The vertex~$x$ is of type~1 and~$z$ is of type~2.
\endcase
\casebody
Let~$vx_kd$ and~$cw_{l-1}z_l$ be triangles associated with the $v$-essential
edges~$vx_k$ and $w_{l-1}z_l$ respectively, where $v\neq c\in V_{\sigma}$.
Let 
$$
\cB'=\cB''\cup\{vx_kd,cw_{l-1}z_l\}.
$$
The proof that~$vx_kd$ is edge-disjoint
from~$\cB'\setminus\{vx_kd,cw_{l-1}z_l\}$ is as in Case 1, and the
fact that~$v\neq c$ 
and~$x_k\neq w_{l-1}$ is enough to prove that~$cw_{l-1}z_l$  
is edge-disjoint from~$vx_kd$. Also, $cw_{l-1}z_l$ is edge-disjoint from
all of~$\cB'\cap\cB$ since~$w_{l-1}z_l$ is essential for~$\cB$
and~$w_{l-1}z_l\in(E(P(x))\cup E(P(z)))\cap M_v$, and from~$\cB'\setminus\cB$
since~$w_{l-1}z_l\notin(E(P(x))\cup E(P(z)))\setminus M_v$ and~$c\neq
v$. Therefore~$\cB'$ is an independent set of triangles that satisfies~(2.1). 
\endcasebody

\case3. The vertices~$x$ and~$z$ are both of type 2. 
\endcase
\casebody
Let~$y_{k-1}x_kd$ and~$cw_{l-1}z_l$ be triangles associated with the
$v$-essential edges~$y_{k-1}x_k$ and~$w_{l-1}z_l$ respectively, where~$c$,
$d\in V_{\sigma}$ and~$v\neq c$, $d$.  This time let
$$
\cB'=\cB''\cup\{y_{k-1}x_kd,cw_{l-1}z_l\}.
$$
%
The proof that
$y_{k-1}x_kd$ and~$cw_{l-1}z_l$ are edge-disjoint from all
of~$\cB'\cap\cB$ is as before.  Also, $w_{l-1}z_l$, $y_{k-1}x_k\notin
E(P(x))\cap E(P(z)))\setminus M_v$ and $c$, $d\neq v$ imply that~$y_{k-1}x_kd$
and~$cw_{l-1}z_l$ are edge-disjoint
from~$\cB'\setminus(\cB\cup\{y_{k-1}x_kd,cw_{l-1}z_l\})$.  Finally,
$y_{k-1}x_kd$ and~$cw_{l-1}z_l$ share no edges since~$y_{k-1}x_k$
and~$w_{l-1}z_l$ are distinct independent edges in~$H_v$.  Therefore~$\cB'$ is
indeed an independent set of triangles satisfying~(2.1).
%\endcasebody

This completes the proof of assertion~({\it i\/}).
\enddemo

\demo{Proof of {\rm({\it ii\/})}} We start by showing that~$C$ is a
transversal for~$G$.  Let~$T=vxy\in\cT(G)$ where~$v\in
V_{\sigma}$, $y\in V_{\sigma+1}$, and $x\in V_{\sigma+2}$, and
suppose~$E(T)\cap E_{\sigma}(\cB)=\emptyset$, that is~$xy\notin M_v$.  If~$y$
were not incident with an edge of~$M_v$, then~$xv$ would be essential
for~$\cB$, and hence~$x\in\bV(H_v)$ and so~$E(T)\cap C_2\neq\emptyset$.
Similarly we are done if~$x$ were not incident with an edge of~$M_v$, so we
may assume that~$zx$ and~$wy$ are in~$M_v$ for some~$w\in V_{\sigma+2}$ and
$z\in V_{\sigma+1}$.  Now if~$wy$ were essential for~$\cB$, then the
alternating path $P(x)=zxyw$ would show that~$x$ is $v$-essential, and
hence~$vx\in E(T)\cap C_2$.  Clearly we may also assume that~$y$ is not
$v$-essential.  Finally, to show that~$vy\in C_3$, we need to show that~$w$ is
not $v$-essential, so suppose on the contrary that it is.  Then there exists
an alternating path $P(w)=ywy_1x_2y_2\dots x_k$ satisfying the required
conditions.  Then we claim that~$x$ is $v$-essential with path $P(x)=zxP(w)$.
The only condition we need to check is that~$P(x)$ is really a path, {\it
  i.e.\/}, we do not have~$x=x_i$ for some~$i\in\{2,\dots,k\}$ or~$z=y_j$ for
some~$j\in\{1,\dots,k-1\}$.  If the second of these holds then also~$x=x_{j+1}$
since~$zx\in M_v$ is the only edge in $M_v$ incident with~$z$.  But as noted
before, if~$w$ is of type~1 then~$x_i$ is also $v$-essential
for~$i=2,\dots,k$, which would imply that~$x$ is $v$-essential.  Similarly
if~$w$ is of type~2 and~$x=x_j$ for some~$j\in\{2,\dots,k-1\}$ then we are
finished.  Finally if~$w$ is of type~2 and~$x=x_k$ then $P(y)=wyx_ky_{k-1}$
shows that~$y$ is $v$-essential.  Therefore if~$x$ and~$y$ are not
$v$-essential then $vy\in E(T)\cap C_3$.  Hence~$C$ is a transversal
of~$\cT(G)$.  

Now~$|C|=|\cB|+|C_2|+|C_3|$, and by~({\it i\/}) we have that $|C_2|=\sum_{v\in
  V_{\sigma}}|\bV(H_v)|$ and~$|C_3|=\sum_{v\in
  V_{\sigma}}\big(|M_v|-|\bV(H_v)|-|M_v\cap\bE_{\sigma}(\cB)|\big)$.  Hence
$$
|C|=|\cB|
     +\sum_{v\in V_{\sigma}}\big(|M_v|-|M_v\cap\bE_{\sigma}(\cB)|\big)
   =2|\cB|-\nu_{\sigma}(\cB), 
$$  
proving~({\it ii\/}).
\enddemo
This completes the proof of Lemma~{\LemmaB}.
\qed
\enddemo

\demo{Proof of Lemma {\LemmaC}}
We start by proving that~$x_j\neq w_r$ for all~$j$ and~$r$.  First note
that~$x\neq w_r$ for any~$r$ since~$P(z)$ is a path.  Now suppose
that~$x_j=w_r$ for some~$j\in\{2,\dots,k-1\}$
and~$r\in\{1,\dots,l-2\}$.  Then since~$M_v$ is a matching and
both~$y_{j-1}x_j$ and~$w_rz_{r+1}\in M_v$, we have also
that~$y_{j-1}=z_{r+1}$.  But then~$y_{j-1}x_j\in M_v$,
and~$P(x_j)=y_{j-1}x_jy_j\dots x_k$ and~$P(y_{j-1})=w_rz_{r+1}w_{r+1}\dots
z_l$ show that~$x_j$ and~$y_{j-1}$ are $v$-essential.  Therefore the
triple~$(x_jy_{j-1},P(x_j),P(y_{j-1}))$ is a better choice
than~$(xz,P(x),P(z))$, which is a contradiction.

Hence~$x_j=w_r$ can happen only if~$j=k$ or~$r=l-1$.  To complete the
argument we shall now need to consider several cases according to the type
of~$x$ and~$z$.  First note that the above argument is also valid, {\it
  i.e.\/}, $P(x_j)$ and~$P(y_{j-1})$ are `valid' alternating paths
if~$x_j=w_r$ and any of the following hold:
\roster
\item"$\bullet$" $j=k$, $r\neq l-1$, $x$ is of type 1 and $z$ is of either
  type,
\item"$\bullet$" $r=l-1$, $j\neq k$, $z$ is of type 1 and $x$ is of either
  type,
\item"$\bullet$" $j=k$, $r=l-1$, and both $x$ and $z$ are of type 1.
\endroster

\noindent We next consider the case in which~$j=k$, $r\neq l-1$, and~$x$ is of
type~2, {\it i.e.\/}, $y_{k-1}x_k\in M_v$ is essential for~$\cB$.  Then again
we must have~$w_rz_{r+1}=y_{k-1}x_k\in M_v$ essential for~$\cB$, and
so~$P'(z)=xzw_1\dots w_rz_{r+1}$ is a valid shorter path for~$z$,
contradicting the fact that~$k+l$ is minimal.  Similarly, if~$r=l-1$, $j\neq
k$, and~$z$ is of type 2 then $w_{l-1}z_l=y_{j-1}x_j$ and~$P'(x)=zxy_1x_2\dots
y_{j-1}x_j$ is a valid shorter path for~$x$.

The remaining cases have~$j=k$ and~$r=l-1$, so $y_{k-1}x_k=w_{l-1}z_l$.
If~$x$ is of type~2 and~$z$ is of type~1, then the triangle
$vx_ky_{k-1}\in\cB$ has two essential edges~$y_{k-1}x_k$ and~$vz_l$.
Let~$y_{k-1}z_la$ and~$vz_lb$ be triangles associated with these essential
edges, where~$v\neq a\in V_{\sigma}$.
Then~$\cB'=\big(\cB\setminus\{vx_ky_{k-1}\}\big)\cup\{y_{k-1}x_ka,vz_lb\}$ is
an independent set of triangles of size~$|\cB|+1$ satisfying~(2.1) of our lemma.
Now if~$x$ is of type~1 and~$z$ is of type~2, then the same argument applies
with the edges~$y_{k-1}x_k$ and~$vx_k$ that are essential for~$\cB$.
Therefore the last possibility is that~$x$ and~$y$ are both of type~2.  We
shall show that in this case~$\cB'$ as in~(2.1) exists.
Let~$cy_{k-1}x_k=cw_{l-1}z_l$ be a triangle associated with the essential
edge~$y_{k-1}x_k$, so~$v\neq c\in V_{\sigma}$.  Let
$$
\cB'=\cB''\cup\{cy_{k-1}x_k\},
$$
%
where $\cB''$ is as defined in (**).
Here the triangle~$cy_{k-1}x_k$ is edge-disjoint from
any~$T\in\cB'\setminus(\cB'_v\cup\{cy_{k-1}x_k\})=\cB\setminus\cB_v$
since~$cy_{k-1}x_k$ is associated to the essential edge~$y_{k-1}x_k$
of~$\cB$, and is edge-disjoint from 
any~$T\in\cB'_v$ by construction.  Therefore~$\cB'$ is an independent
set of triangles of size $|\cB|+1$, and also the edge condition in~(2.1)
follows for $\cB'$ from~(**).
This contradiction shows that~$x_j\neq w_r$ for any~$j$
and~$r$.  A similar argument shows that~$y_j\neq z_r$ for any~$j$ and~$r$, and
so $P(x)$ and $P(z)$ are vertex-disjoint apart from~$x$ and~$z$, proving
Lemma~{\LemmaC}.
\qed
\enddemo

\head\S2. Proof of the Main Result
\endhead

We now proceed to prove our main result, Theorem~{\ThmA} below.  In the
sequel, the edge of colour~$\sigma$ in a triangle~$T$ is denoted
by~$e_\sigma(T)$.

\proclaim{Theorem~{\ThmA}} Let $G$ be a tripartite graph. Then
$\tau(G)\leq\alpha\nu(G)$, where $\alpha=(38+\sqrt{1948})/42<1.956$.
\endproclaim
\demo{Proof}
The proof is by induction on~$\nu=\nu(G)$.  The case $\nu=1$ is immediate, and
hence we assume that~$\nu=\nu(G)\geq2$ and that our theorem holds for
graphs~$G'$ with~$\nu(G')<\nu$.  Let~$\cB_0$ be a fixed independent set of
triangles in~$G$ of size~$\nu$.  Our first aim is to construct a second large
independent set~$\cB_1$ of triangles of~$G$.  Let~$G'$ denote the graph
obtained from~$G$ by deleting all edges in~$E_1(\cB_0)$, let~$\cB'$ be an
independent set of triangles of~$G'$ of maximum size, and let~$\nu'=|\cB'|$.

\case1. $\nu'=\nu$
\endcase
\casebody
In this case, we claim that~$\tau(G)\leq7\nu/4<\alpha\nu$, which completes
the induction step.  To prove the claim, let   
$$
C_0=E_2(\cB_0)\cup E_2(\cB')\cup\bE_3(\cB_0)\cup\bE_3(\cB')
$$
and let~$T\in\cT(G)$.  Suppose that~$E(T)\cap(E_2(\cB_0)\cup
E_2(\cB'))=\emptyset$.  Since~$\nu'=\nu$ it is clear that~$T$ must
contain an edge of~$E(\cB_0)$ and an edge of~$E(\cB')$.  But~$E_1(\cB_0)\cap
E_1(\cB')=\emptyset$ by construction, so for one of~$\cB=\cB_0$ or~$\cB'$ we
have~$E(T)\cap E_1(\cB)=\emptyset$.  Therefore~$E(T)\cap
E_3(\cB)\neq\emptyset$, and by definition~$T$ shows that~$e_3(T)$ is essential
for~$\cB$. Thus~$E(T)\cap \bE_3(\cB)\neq\emptyset$, and so we have shown  
that~$C_0$ is a transversal.

To estimate~$|C_0|$, we first consider~$|E_2(\cB')\setminus E_2(\cB_0)|$.
Note that if~$T\in\cB'$ and~$e_2(T)\notin E_2(\cB_0)$ then~$T$ shows
that~$e_3(T)$ is essential for~$\cB_0$.  Since any two such~$T$ are 
edge-disjoint, we see that there are at most~$\nu_3(\cB_0)=|\bE(\cB_0)|$ such  
triangles.  Therefore~$|E_2(\cB')\setminus E_2(\cB_0)|\leq\nu_3(\cB_0)$, and
hence $|C_0|\leq\nu+2\nu_3(\cB_0)+\nu_3(\cB')$.  Now, by Lemma~{\LemmaB}, we
are finished if~$\nu_3(\cB_0)\geq\nu/4$ or~$\nu_3(\cB')\geq\nu/4$, so let us
assume that~$\nu_3(\cB_0)$, $\nu_3(\cB')<\nu/4$.  But then~$|C_0|\leq7\nu/4$,
which proves the claim, and hence this case is finished. 
\endcasebody

\case2. $\nu'<\nu$
\endcase
\casebody
In this case, by induction there exists a transversal~$C'$ of~$G'$ of size at
most~$\alpha\nu'$.  Notice that~$C'\cup E_1(\cB_0)$ is a transversal for~$G$
of size at most~$\nu+\alpha\nu'$, and so we may assume
that~$\nu+\alpha\nu'>\alpha\nu$, that is, that~$\nu'>(\alpha-1)\nu/\alpha$.
We now consider~$\cB'$ as an independent set of triangles in~$G$.  We apply
Lemma~{\LemmaA} repeatedly with $\sigma=2$ and $\sigma=3$ to obtain a
sequence~$\cB'=\cB^1,\cB^2,\dots,\cB^k$ 
of independent families of triangles in~$G$, where for each~$i=1,\dots,k-1$ we
have $|\cB^{i+1}|=|\cB^i|+1$ and $E_1(\cB^i)\subset E_1(\cB^{i+1})$,
and~$\cB^k$ satisfies~(1.2) of Lemma~{\LemmaA}.  Let~$\nu''=|\cB^k|$.  Then by
Lemma~{\LemmaA} we know that~$\tau(G)\leq2\nu''$, and so we may assume
that~$\nu''>\alpha\nu/2$.

Finally, to obtain~$\cB_1$, we apply Lemma~{\LemmaB} repeatedly with
$\sigma=2$ and $\sigma=3$ to obtain a
further sequence~$\cB^k,\cB^{k+1},\dots,\cB^f=\cB_1$ of independent families
of triangles of~$G$, where for each~$i=k,\dots,f-1$ we
have~$|\cB^{i+1}|=|\cB^i|+1$ and $|E_1(\cB^i)\cap
E_1(\cB^{i+1})|\geq|\cB^i|-1$. Then by~(2.2) of Lemma 2 we have 

\assertion(3)$\tau(G)\leq 2|\cB_1|-\nu_{\sigma}(\cB_1)$ for both
$\sigma=2$ and $\sigma=3$. 
\endassertion

Let~$\nu_1=|\cB_1|$.  Clearly~$\nu_1\leq\nu$. By construction we have
that~$|E_1(\cB_1)\cap E_1(\cB')|\geq\nu'-(\nu_1-\nu'')$, and so 
$$
|E_1(\cB_1)\cap E_1(\cB_0)|
  \leq\nu_1-|E_1(\cB_1)\cap E_1(\cB')|\leq2\nu_1-\nu'-\nu''.
  \leqno{(4)}
$$ 

Our aim is to choose a set $C$ of edges from $E(\cB_0)\cup E(\cB_1)$
that will be a transversal of $G$ of suitable size.
We shall select $C$ based on the following assertion.

\assertion($\dag$) One of the following holds:
\roster
\item"({\it a\/})" $|E_2(\cB_1)\setminus E_2(\cB_0)|
   \leq\nu_3(\cB_0)+{1\over2}\nu_1(\cB_0)+\nu-{1\over2}(\nu'+\nu'')$, or
\item"({\it b\/})" $|E_3(\cB_1)\setminus E_3(\cB_0)|
   \leq\nu_2(\cB_0)+{1\over2}\nu_1(\cB_0)+\nu-{1\over2}(\nu'+\nu'')$. 
\endroster
\endassertion
\proofofassertion 
Consider first the set~$\cS$ of triangles~$T\in\cB_1$ for which~$e_1(T)\in
E_1(\cB_1)\cap E_1(\cB_0)$.  Note that clearly~$|\cS|=|E_1(\cB_1)\cap
E_1(\cB_0)|$.  If~$T\in\cS$ and both~$e_2(T)\notin E_2(\cB_0)$ and 
$e_3(T)\notin E_3(\cB_0)$, then~$T$ shows that~$e_1(T)$ is 
essential for~$\cB_0$.  Therefore the number of such triangles~$T$
is at most~$\nu_1(\cB_0)$.  Hence at least~$|E_1(\cB_1)\cap  
E_1(\cB_0)|-\nu_1(\cB_0)$ of the triangles~$T\in\cS$ are such that
either~$e_2(T)\in E_2(\cB_0)$ or~$e_3(T)\in E_3(\cB_0)$. Thus for one
of $\sigma=2$ or $\sigma=3$ we have
that at most~$\nu_1(\cB_0)+(|E_1(\cB_1)\cap
E_1(\cB_0)|-\nu_1(\cB_0))/2$ triangles in $\cS$ are such
that~$e_{\sigma}(T)\notin E_{\sigma}(\cB_0)$.       
Let us first suppose that here $\sigma=2$, and we
proceed to prove that~({\it a\/}) holds. The proof for~({\it b\/}) is exactly
the same if $\sigma=3$.

Now we look at~$\cB_1\setminus\cS$.  If~$T\in\cB_1\setminus \cS$
then~$e_1(T)\notin E_1(\cB_0)$.  If also~$e_2(T)\notin E_2(\cB_0)$ then~$T$
shows that~$e_3(T)$ is essential for~$\cB_0$.  Thus  
the number of~$T\in\cB_1\setminus \cS$ for which~$e_2(T)\notin E_2(\cB_0)$
is at most~$\nu_3(\cB_0)$.  Hence altogether the number of~$T\in\cB_1$
for which~$e_2(T)\notin E_2(\cB_0)$ is at most~$\nu_3(\cB_0)+(|E_1(\cB_1)\cap
E_1(\cB_0)|+\nu_1(\cB_0))/2$, that is 
$$
|E_2(\cB_1)\setminus E_2(\cB_0)|
  \leq\nu_3(\cB_0)+{1\over2}\nu_1(\cB_0)+\nu-{1\over2}(\nu'+\nu''), 
$$
where we use (4). This proves~({\it a\/}), and hence assertion~($\dag$).
\endproofofassertion

To finish the proof of~Case 2, we construct a suitable
transversal~$C$ for~$G$.  In what follows, we assume without loss of
generality that~({\it a\/}) holds in assertion~($\dag$). Let
$$
C=\bE_3(\cB_0)\cup\bE_3(\cB_1)
   \cup E_2(\cB_0)\cup E_2(\cB_1)
   \cup(E_1(\cB_0)\cap E_1(\cB_1)),
$$ 
and we claim that~$C$ is a transversal of~$\cT(G)$.  To see this, suppose
that~$T\in\cT(G)$ and~$E(T)\cap\big\{E_2(\cB_0)\cup
E_2(\cB_1)\cup(E_1(\cB_1)\cap E_1(\cB_0))\big\}=\emptyset$.  Then for one
of~$\cB=\cB_0$ or~$\cB_1$, we have that~$e_1(T)\notin E_1(\cB)$
and~$e_2(T)\notin E_2(\cB)$.  Hence~$e_3(T)$ is essential for~$\cB$,
and~$E(T)\cap(\bE_3(\cB_0)\cup\bE_3(\cB_1))\neq\emptyset$, which shows
that~$C$ is indeed a transversal for~$G$.

Now it only remains to estimate~$|C|$. Using~(4) and
assertion~($\dag$)({\it a\/}), we have  
$$
\eqalign{
|C|&\leq\nu_3(\cB_0)+\nu_3(\cB_1)+\nu \cr
   &\qquad\quad+\nu_3(\cB_0)+{1\over2}\nu_1(\cB_0)+\nu
                 -{1\over2}(\nu'+\nu'')+2\nu-\nu'-\nu''\cr
   &=2\nu_3(\cB_0)+\nu_3(\cB_1)+{1\over2}\nu_1(\cB_0)
       +4\nu-{3\over2}(\nu'+\nu'').
}
$$
Now, by
(3) and  Lemma~{\LemmaB}, for each
pair~$(\sigma,i)\in\{(3,1),(3,0),(1,0)\}$ 
there is a transversal of~$\cT(G)$ of size at
most~$2\nu-\nu_{\sigma}(\cB_i)$.  Therefore we may assume that each
of~$\nu_3(\cB_0)$, $\nu_1(\cB_0)$, and $\nu_3(\cB_1)$ is less
than~$(2-\alpha)\nu$.  Further recall that~$\nu''>\alpha\nu/2$ 
and~$\nu'>(\alpha-1)\nu/\alpha$.  Hence 
$$
\eqalign{
|C|&\leq{7\over2}(2-\alpha)\nu+4\nu-{3\over2}(\nu'+\nu'')\cr
   &\qquad\qquad\leq\nu\(11-{7\over2}\alpha
                -{3\over2}\({\alpha-1\over\alpha}+{1\over2}\alpha\)\)
    ={\nu\over4\alpha}(6+38\alpha-17\alpha^2)\leq\alpha\nu. 
}
$$ 
This finishes the induction step in this case and the theorem is proved. 
%\endcasebody
\qed
\enddemo

We close with the remark that finding examples of tripartite graphs~$G$
with $\tau(G)/\nu(G)$ much larger than~$1$ seems difficult. The   
graphs~$H_1$ and~$H_2$ in Figure~1 are such
that~$\tau(G)=5\nu(G)/4$.  Therefore any graph~$G$ whose blocks are 
isomorphic to copies of $K^2$, $H_1$ or $H_2$ will be such that
$\tau(G)\geq5\nu(G)/4$. 
\input pictex
\topinsert
\hrule
\vskip3\jot
\newbox\picA
\setbox\picA=\hbox{
\beginpicture % tripartite Tuza pics
\setcoordinatesystem units <.03in,.03in> 
\setplotarea x from 65 to 140 , y from 20 to 60
\setlinear\plot 115 50 130 45  120 63 115 50 90 63 120 63 95 50 90 63 80 45 95
50 90 25 80 45 105 40 90 25 120 25 105 40 130 45 120 25 115 50 /
\put{$\bullet$} at 115 50
\put{$\bullet$} at 90 63 
\put{$\bullet$} at 80 45 
\put{$\bullet$} at 90 25 
\put{$\bullet$} at 120 25 
\put{$\bullet$} at 130 45 
\put{$\bullet$} at 120 63
\put{$\bullet$} at 95 50 
\put{$\bullet$} at 105 40 
%\put{$v_1$} at 112 50
%\put{$v_2$} at 85 62
%\put{$v_3$} at 76 44
%\put{$v_4$} at 89 20
%\put{$v_5$} at 119 20 
%\put{$v_6$} at 133 44
%\put{$v_7$} at 123 62
%\put{$v_8$} at 97 49
%\put{$v_9$} at 104 43
\endpicture}
\newbox\picB
\setbox\picB=\hbox{
\beginpicture % PicTeX diagram for pebbling paper
\setcoordinatesystem units <.029in,.029in> 
\setplotarea x from 65 to 150 , y from 20 to 60
\setlinear\plot 104 62  123 62 133 44 119 25 89 25 75  44 104 35 84 62 104
50 104 62 /
\plot 104 62 75  44 84  62 /
\plot 75  44 104 50  123 62 104 35 133 44 104 50 /
\plot 89 25 104 35   119 25 /
%\put{$v_1$} at 99 62
%\put{$v_2$} at 81  62 
%\put{$v_3$} at 72  44
%\put{$v_4$} at 89  20
%\put{$v_5$} at 119 20
%\put{$v_6$} at 136 44
%\put{$v_7$} at  126 62
%\put{$v_8$} at 104 47
%\put{$v_9$} at 104 38 
\put{$\bullet$} at 104 62
\put{$\bullet$} at 84  62 
\put{$\bullet$} at 75  44
\put{$\bullet$} at 89 25
\put{$\bullet$} at 119 25
\put{$\bullet$} at 133 44
\put{$\bullet$} at 123 62
\put{$\bullet$} at 104 50
\put{$\bullet$} at 104 35 
\endpicture}
\centerline{\beginpicture % PicTeX diagram for pebbling paper
\setcoordinatesystem units <.03in,.03in> 
\setplotarea x from 0 to 140 , y from 20 to 60
\put{\copy\picA} at 20 50
\put{\copy\picB} at 95 50
\endpicture}
\vskip-5\jot
\centerline{{\bf Figure 1.} The graphs~$H_1$ and~$H_2$}
\vskip3\jot
\hrule
\endinsert 

\Refs
\ref\key\refnoFuSurvey
\by F\"uredi, Z.
\paper Matchings and covers in hypergraphs
\jour Graphs and Combinatorics
\vol4
\yr1988
\pages115--206
\endref

\ref\key\refnoHaxellRy
\by Haxell, P.E.
\paper A note on a conjecture of Ryser
\jour\PMH\vol30
\yr1995
\pages73--79
\endref

\ref\key\refnoKri
\by Krivelevich, M.
\paper On a conjecture of Tuza about packing and covering of triangles 
\jour\DM\vol142
\yr195
\pages281--286
\endref

\ref\key\refnoTuConj
\by\Tu
\paper Conjecture
\inbook Finite and Infinite Sets (Eger, Hungary~1981)
\bookinfo Proc. Colloq. Math. Soc. J. Bolyai, Vol.~37
\eds Hajnal, A., \Lo, S\'os, V.T.
\publ North-Holland
\publaddr Amsterdam
\yr1984
\page888
\endref

\ref\key\refnoTuB
\bysame
\paper Ryser's conjecture for transversals of $r$-partite hypergraphs 
\jour Ars Combinatoria\vol{16(B)}
\yr1983
\pages201--209
\endref

\ref\key\refnoTuC
\bysame
\paper A conjecture on triangles of graphs
\jour\GC\vol6
\yr1990
\pages373--380 
\endref

\endRefs
\enddocument


