\documentclass[12pt]{article} \usepackage{e-jc} \specs{P1.38}{21(1)}{2014} \usepackage{amsthm,amsmath,amssymb} \usepackage{graphicx} %\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % %\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} %\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \newcommand{\TR}[1]{\mbox{$\tau(#1)$}} \newcommand{\clique}{w} \newenvironment{unnumbered}[1]{\trivlist \item [\hskip \labelsep {\bf #1}]\ignorespaces\it}{\endtrivlist} \title{\bf A new lower bound on the\\ independence number of a graph\\ and applications } \author{Michael A. Henning \\ \small Department of Mathematics \\[-0.8ex] \small University of Johannesburg \\[-0.8ex] \small Auckland Park, 2006 South Africa\\ \small\tt mahenning@uj.ac.za \\ \and Christian L\"{o}wenstein\\ \small Institute of Optimization and Operations Research \\[-0.8ex] \small Ulm University \\[-0.8ex] \small Ulm 89081, Germany \\ \small\tt christian.loewenstein@uni-ulm.de \\ \and Justin Southey \\ \small Department of Mathematics \\[-0.8ex] \small University of Johannesburg \\[-0.8ex] \small Auckland Park, 2006 South Africa\\ \small\tt just.so@presentable.me \\ \and Anders Yeo \\ \small Engineering Systems and Design \\[-0.8ex] \small Singapore University of Technology and Design \\[-0.8ex] \small 20 Dover Drive Singapore, 138682, Singapore \\[-0.8ex] \small \textit{and} \\[-0.8ex] \small Department of Mathematics \\[-0.8ex] \small University of Johannesburg \\[-0.8ex] \small Auckland Park, 2006 South Africa\\ \small\tt andersyeo@gmail.com } \date{\dateline{Jul 25, 2013}{Feb 11, 2014}{Feb 21, 2014}\\ \small Mathematics Subject Classifications: 05C65} \begin{document} \maketitle \begin{abstract} The independence number of a graph $G$, denoted $\alpha(G)$, is the maximum cardinality of an independent set of vertices in $G$. The independence number is one of the most fundamental and well-studied graph parameters. In this paper, we strengthen a result of Fajtlowicz [Combinatorica 4 (1984), 35--38] on the independence of a graph given its maximum degree and maximum clique size. As a consequence of our result we give bounds on the independence number and transversal number of $6$-uniform hypergraphs with maximum degree three. This gives support for a conjecture due to Tuza and Vestergaard [Discussiones Math. Graph Theory 22 (2002), 199--210] that if $H$ is a $3$-regular $6$-uniform hypergraph of order $n$, then $\tau(H) \le n/4$. \bigskip\noindent \textbf{Keywords:} independence; clique; transversal \end{abstract} \section{Introduction} In this paper we study independence in graphs. Our main aim is to strengthen a result of Fajtlowicz~\cite{Fa78,Fa84} on the independence of a graph given its maximum degree and maximum clique size. As a consequence of our result we give bounds on the independence number and transversal number of $6$-uniform hypergraphs with maximum degree three. A \emph{hypergraph} $H$ consists of a finite vertex set $V(H)$ and a finite multiset $E(H)$ of edges, where each edge is a subset of $V(H)$. % A hypergraph $H$ has \emph{rank}~$r$ if the largest size of an edge of $H$ is size~$r$. A hypergraph $H$ is $k$-\emph{uniform} if every edge of $H$ has size~$k$. Every graph without loops is a $2$-uniform hypergraph. The \emph{degree} of a vertex $v$ in $H$, denoted by $d_H(v)$ or simply by $d(v)$ if $H$ is clear from context, is the number of edges of $H$ that contain~$v$. The maximum degree among the vertices of $H$ is denoted by $\Delta(H)$. Two edges in $H$ are \emph{overlapping} if they intersect in at least two vertices. Two vertices $x$ and $y$ of $H$ are \emph{adjacent} if some edge of $H$ contains both $x$ and $y$. A set $X$ of vertices in $H$ is a \emph{clique} if every two vertices of $X$ are adjacent in $H$. A $k$-\emph{clique} is a clique in $H$ of size~$k$. The \emph{clique number} $\omega(H)$ is the size of a maximum clique in $H$. % The \emph{neighborhood} of a vertex $v$ in $H$, denoted $N_H(v)$ or simply $N(v)$ if $H$ is clear from context, is the set of all vertices different from $v$ that are adjacent to $v$. % % Two vertices $x$ and $y$ of $H$ are \emph{connected} if there is a sequence $v_0,\ldots,v_k$ of vertices of $H$ with $x=v_0$ and $y=v_k$ in which $v_{i-1}$ is adjacent to $v_i$ for $1 \le i \le k$. A \emph{connected hypergraph} is a hypergraph in which every two vertices are connected. A maximal connected subhypergraph of $H$ is a \emph{component} of $H$. For a subset $X$ of vertices in a hypergraph $H$, let $H[X]$ denote the hypergraph induced by the vertices in $X$, in the sense that $V(H[X])=X$ and $E(H[X]) = \{e \cap X \mid e \in E(H) \mbox{ and } |e \cap X| \ge 1\}$; that is, $E(H[X])$ is obtained from $E(H)$ by shrinking edges $e \in E(H)$ that intersect $X$ to the edges $e \cap X$. If $H$ denotes a hypergraph and $X$ denotes a subset of vertices in $H$, then $H-X$ denotes that hypergraph obtained from $H$ by removing the vertices $X$ from $H$, removing all hyperedges that intersect $X$, and removing all resulting isolated vertices, if any. When $X = \{x\}$, we simply denote $H - X$ by $H - x$. In the literature this is sometimes called \emph{strongly deleting} the vertices in $X$. A \emph{twin} in $H$ is a pair of vertices that are intersected by exactly the same set of edges; that is, a pair of vertices $u$ and $v$ is a twin in $H$ if every edge that contains $u$ also contains~$v$, and every edge that contains $v$ also contains~$u$. The hypergraph $H$ is \emph{twin-free} if it has no twin. Hence if $H$ is twin-free, then for every pair of vertices $u$ and $v$ in $H$, there exists an edge $e$ such that $|e \cap \{u,v\}| = 1$. % A set $S$ of vertices in a hypergraph $H$ is \emph{strongly independent} if no two vertices in $S$ belong to a common edge. The \emph{strong independence number} of $H$, which we denote by $\alpha(H)$, is the maximum cardinality of a strongly independent set in $H$. A subset of vertices in a hypergraph $H$ is a \emph{weakly independent set} if it contains no edge of $H$. A subset $T$ of vertices in a hypergraph $H$ is a \emph{transversal} (also called \emph{vertex cover} or \emph{hitting set} in many papers) if $T$ intersects every edge of $H$. Equivalently, a set of vertices $S$ is transversal in $H$ if and only if $V(H) \setminus S$ is a weakly independent set in $H$. The \emph{transversal number} $\TR{H}$ of $H$ is the minimum size of a transversal in $H$. We note that, $n(H) = \tau(H) + \alpha(H)$. Transversals in hypergraphs are well studied in the literature (see, for example,~\cite{ChMc,CoHeSl79,LaCh90,ThYe07}). Let $G$ be a graph, and let $X$ and $Y$ be disjoint subsets of $V(G)$. The set $E(X,Y)$ is the set of all the edges $xy$, with $x \in X$ and $y \in Y$. For each vertex $u \in V(G)$ let $\clique_G(u)$ denote the size of a largest clique in $G$ containing $u$. We will omit the subscript when $G$ is clear from the context. \section{Independence in Graphs} %In this section, we strengthen a result of Fajtlowicz~\cite{Fa78,Fa84} on the independence of graph given its maximum degree and maximum clique size. We shall prove the following result. The proof we present is similar to that of Fajtlowicz~\cite{Fa78}. However in our proof we carefully choose a maximum independent set $S$ in the graph $G$ such that the number of edges from $S$ to vertices outside $S$ is minimized. With this choice of $S$, we establish a property on the graph $G$ by considering the operation of replacing a vertex in $S$ with a vertex outside $S$ in order to get a smaller number of edges between $S$ and vertices outside $S$. \begin{theorem} \label{main1} If $G$ is a graph of order~$n$ and $p$ is an integer, such that (A) below holds, then $\alpha(G) \ge 2n/p$. %$\alpha(G) \ge \frac{2|V(G)|}{p}$. \begin{center} (A): For every clique $X$ in $G$ there exists a vertex $x \in X$, such that $d(x)< p-|X|$. \end{center} \end{theorem} \begin{proof} Let $G=(V,E)$ be a graph of order $n$ and let $p$ be an integer such that (A) is satisfied. Let $S$ be a maximum independent set in $G$, such that $|E(S,V\setminus S)|$ ($=\sum_{s \in S} d(s)$) is minimized. Let $\alpha_i(S)$ denote the number of vertices in $V \setminus S$ with exactly $i$ neighbors in~$S$. Since $S$ is a maximum independent set we note that $\alpha_0(S)=0$ and therefore the following holds. \begin{equation} \label{eq1} n-|S| = \alpha_1(S) + \alpha_2(S) + \cdots + \alpha_{|S|}(S). \end{equation} Furthermore counting the number of edges in $E(S,V\setminus S)$ we obtain the following. \begin{equation} \label{eq2} \sum_{s \in S} d(s) = \alpha_1(S) + 2 \alpha_2(S) + 3\alpha_3(S) + \cdots + |S|\alpha_{|S|}(S) \end{equation} Multiplying Equation~(\ref{eq1}) by $2$ and subtracting Equation~(\ref{eq2}) we obtain the following. \begin{equation} \label{eq3} 2n-2|S| - \sum_{s \in S} d(s) = \alpha_1(S) - \alpha_3(S) - 2 \alpha_4(S) - \cdots - (|S|-2)\alpha_{|S|}(S) \le \alpha_1(S). \end{equation} For each vertex $s \in S$, let $Y_s$ be the set of all vertices in $V \setminus S$ adjacent to $s$ but to no other vertex of $S$, and so every vertex in $Y_s$ has no neighbor in $S \setminus \{s\}$. If $Y_s$ does not induce a clique, then let $y_1,y_2 \in Y_s$ be non-adjacent vertices and note that $S \cup \{y_1,y_2\} \setminus \{s\}$ is an independent set in $G$ of size greater than $|S|$, a contradiction. Therefore, $Y_s \cup \{s\}$ induces a clique in $G$. Suppose that $d(s) + |Y_s| + 1 \ge p$. If there is a vertex $y \in Y_s$ such that $d(y) < d(s)$, then $(S \cup \{y\}) \setminus \{s\}$ contradicts the minimality of $|E(S,V\setminus S)|$. Therefore, for all $y \in Y_s \cup \{s\}$ we have $d(y) + |Y_s \cup \{s\}| \ge d(s) + |Y_s|+1 \ge p$, a contradiction to (A). This implies that $d(s) + |Y_s| + 1 \le p-1$, as $d(s)$, $|Y_s|$ and $p$ are all integers. We now obtain the following, by Inequality~(\ref{eq3}), \[ 2n \le \alpha_1(S) + \sum_{s \in S} d(s) + 2|S| = \sum_{s \in S} \left( |Y_s| + d(s) + 2 \right) \le |S| p, \] implying that $\alpha(G) = |S| \ge 2n/p$ as desired. \end{proof} \medskip As an immediate consequence of Theorem~\ref{main1} we can prove the following result due to Fajtlowicz~\cite{Fa78} on the independence of graph given its maximum degree and maximum clique size. We remark that in~\cite{Fa84}, Fajtlowicz studies some classes of graphs that achieve equality in the bound of Theorem~\ref{c:Faj}. \begin{corollary} {\rm (\cite{Fa78})} If $G$ is a graph of order~$n$ containing no clique of size $q$, then $\alpha(G) \ge 2n/(\Delta(G)+q)$. \label{c:Faj} \end{corollary} \begin{proof} Let $G$ be a graph of order~$n$ containing no clique of size $q$ and let $p=\Delta(G)+q$. For every clique $X$ in $G$ and for all vertices $x \in X$, we have $d(x) < \Delta(G) +1 \le \Delta(G) + q - |X| = p - |X|$, and therefore condition (A) holds in Theorem~\ref{main1}. By Theorem~\ref{main1} we have that $\alpha(G) \ge 2n/p = 2n/(\Delta(G)+q)$. \end{proof} \section{Independence in hypergraphs of rank at most~$6$} In this section we apply our main result, namely Theorem~\ref{main1}, to $3$-regular, $6$-uniform hypergraphs as there is a very interesting conjecture for this case, namely the Tuza-Vestergaard Conjecture which we state later. The application illustrates the power of our main result. However we remark that Theorem~\ref{main1} can be used in the cases where the regularity is less than the uniformity. We will prove the following theorem. We remark that the twin-free condition in Theorem~\ref{main2} is necessary, since otherwise the result is not true. Consider, for example, the Fano-plane, where each vertex gets duplicated. The resulting hypergraph, $H$, is a $3$-regular $6$-uniform hypergraph on $n = 14$ vertices, with strong independence number~$\alpha(H) = 1 < 2n/23$. \begin{theorem} \label{main2} If $H$ is a twin-free $3$-regular hypergraph of order~$n$ and rank at most~$6$, then $\alpha(H) \ge 2n/23$. %Any $3$-regular hypergraph $H$ of rank at most $6$ and without twins contains a strongly independent set of size at least $2|V(G)|/23$. \end{theorem} Before giving a proof of Theorem~\ref{main2} we need a number of preliminary results. Let $H$ be a hypergraph of rank at most~$6$. % For a set $X$ of vertices in the hypergraph $H$, let \[ \theta_X(H) = \max |X \cap e \cap f|, \] \noindent where the maximum is taken over all distinct edges $e$ and $f$ in $H$. Let $e_1$ and $e_2$ be two (fixed) edges in $H[X]$ such that $\theta_X(H) = |X \cap e_1 \cap e_2|$ and let $Y$ and $Z$ be defined by \[ Y = X \setminus (e_1 \cup e_2) \hspace*{0.5cm} \mbox{and} \hspace*{0.5cm} Z = X \cap e_1 \cap e_2. \] \noindent We note that, $\theta_X(H) = |Z|$. %and $Z = e_1 \cap e_2$. %For a vertex $x \in X$, we define $\Xbar_x$ to be the set of vertices in $X$ not adjacent to $x$; that is, $\Xbar_x = X \setminus N_{H[X]}[x]$. Let $\Xbar = \max |\Xbar_x|$, where the maximum is taken over all vertices $x \in X$. We proceed further with a series of five lemmas that will prove useful when proving our main result. \begin{lemma} Let $H$ be a $3$-regular hypergraph of rank at most~$6$ and let $X$ be a clique of size at least~$8$ in $H$. Then the following hold. \\ \indent {\rm (a)} $|Z| \ge 2$. \\ \indent {\rm (b)} If $H$ is twin-free and $|Y| \ge 2$, then $|Z| = 2$. \\ \indent {\rm (c)} If $H$ is twin-free, then $|Y| \le 2$. \label{useful} \end{lemma} \begin{proof} (a) Let $x \in X$ and let $f_1,f_2,f_3$ be the three edges incident with $x$ in $H[X]$. If any two of these edges overlap, then $|Z| \ge 2$, as desired. Hence we may assume that $f_i \cap f_j = \{x\}$ for $1 \le i < j \le 3$. Since $H$ has rank at most~$6$, $|f_i| \le 6$ for $1 \le i \le 3$. Renaming edges if necessary, we may assume that $|f_1| \ge |f_2| \ge |f_3|$. Since $|X| \ge 8$, we note that $|f_1| \ge 4$ and $|f_2| \ge 2$. Let $v \in f_2 \setminus \{x\}$. Since $X$ is a clique, the vertex $v$ is adjacent to every vertex in $f_1$. However, $d_H(v) = 3$ and the edge $f_2$ does not intersect $f_1 \setminus \{x\}$. Hence one of the two remaining edges, $g_1$ say, containing $v$ in $H[X]$ must contain at least two vertices of $f_1 \setminus \{x\}$. But then $|f_1 \cap g_1| \ge 2$, and so $|Z| \ge 2$. (b) Suppose to the contrary that $H$ is twin-free and $|Y| \ge 2$, but $|Z| \ge 3$. Let $\{z_1,z_2,z_3\} \subseteq Z$. For $i = 1,2,3$, let $g_i$ be the edge in $H[X]$ containing $z_i$ that is different from $e_1$ and $e_2$. Since $H$ is twin-free, we note that $z_i \notin g_j$ for $1 \le i, j \le 3$ and $i \ne j$. Let $\{y_1,y_2\} \subset Y$. Since $X$ is a clique, every vertex in $Y$ is adjacent to every vertex in $Z$. Thus, $\{y_1,y_2\} \subset g_i$ for $i = 1,2,3$. But then $y_1$ and $y_2$ are twins, a contradiction. Therefore, $|Z| \le 2$. By part~(a), $|Z| \ge 2$. Consequently, $|Z| = 2$. (c) Suppose to the contrary that $H$ is twin-free, but $|Y| \ge 3$. By Part~(b), $|Z| = 2$. Let $Z_1 = \{z_1,z_2\}$. For $i = 1,2$, let $g_i$ be the edge in $H[X]$ containing $z_i$ that is different from $e_1$ and $e_2$. Since $H$ is twin-free, we note that $z_1 \notin g_2$ and $z_2 \notin g_1$. Since $X$ is a clique, every vertex in $Y$ is adjacent to every vertex in $Z$. Thus, $Y \subset g_i$ for $i = 1,2$. But then $|Z| = \theta_X(H) \ge |X \cap g_1 \cap g_2| \ge |Y| \ge 3$, contradicting Part~(b). \end{proof} \begin{lemma} If $H$ is a twin-free $3$-regular hypergraph of rank at most~$6$, then $\omega(H) \le 10$. \label{clique} \end{lemma} \begin{proof} Suppose to the contrary that $\omega(H) \ge 11$. Let $X$ be a clique of size~$11$ in $H$, and let $H[X]$, $\theta_X(H)$, $e_1$, $e_2$, $Y$ and $Z$ be as defined earlier. Then, $11 = |X| = |e_1 \cup e_2| + |Y| = |e_1| + |e_2| - |Z| + |Y|$. By Lemma~\ref{useful}(a), $|Z| = \theta_X(H) \ge 2$. Since $H$ has rank at most~$6$, $|e_1| + |e_2| \le 6 + 6 = 12$. If $|Z| \ge 3$, then $11 \le 12 - 3 + |Y|$, and so $|Y| \ge 2$, contradicting Lemma~\ref{useful}(b). Therefore, $|Z|=2$, implying that $11 \le 12-2 +|Y|$, or, equivalently, $|Y| \ge 1$. Let $y \in Y$ and let $Z = \{z_1,z_2\}$. For $i = 1,2$, let $g_i$ be the edge in $H[X]$ containing $z_i$ that is different from $e_1$ and $e_2$. Since $H$ is twin-free, we note that $z_1 \notin g_2$ and $z_2 \notin g_1$. Further since $X$ is a clique, we have that $y \in g_1$ and $y \in g_2$. Let $g_3$ denote the remaining edge containing $y$ in $H[X]$. For $i = 1,2$, let $e_i' = e_i \setminus Z$. Renaming the edges $e_1$ and $e_2$, if necessary, we may assume that $|e_1'| \ge |e_2'|$. If $|e_1'| \le 3$, then $|e_1 \cup e_2| \le 8$, implying that $|Y| \ge 3$, contradicting Lemma~\ref{useful}(c). Hence, $|e_1'| \ge 4$. However, $|e_1'| = |e_1| - |Z| \le 6 - 2 = 4$. Consequently, $|e_1'| = 4$. We note therefore that either $|Y| = 1$, in which case $|e_2'| = 4$, or $|Y| = 2$, in which case $|e_2'| = 3$. Hence, $|e_2'| \ge 3$. If neither the edge $g_1$ nor the edge $g_2$ intersects $e_2'$, then $e_2' \subset g_3$. But then $\theta_X(H) \ge |e_2 \cap g_3| \ge |e_2'| \ge 3$, a contradiction. Therefore renaming the vertices $z_1$ and $z_2$, if necessary, we may assume that $g_1$ intersects $e_2'$. Let $w \in e_2' \cap g_1$. Since $2 = \theta_X(H) \ge |e_1 \cap g_1|$, we note that the edge $g_1$ contains $z_1$ and at most one vertex of $e_1'$. But then the edge, $e_w$ say, that contains $w$ and is different from $e_2$ and $g_1$, contains at least three vertices of $e_1'$, implying that $\theta_X(H) \ge |e_1 \cap e_w| \ge |e_1'| - 1 = 3$, a contradiction. \end{proof} \begin{lemma} If $H$ is a twin-free $3$-regular hypergraph of rank at most~$6$ and $X$ is a $10$-clique in $H$, then there exists a vertex $x \in X$ with $|N(x)| \le 12$. \label{clique10} \end{lemma} \begin{proof} Let $X$ be a $10$-clique in $H$, and let $H[X]$, $\theta_X(H)$, $e_1$, $e_2$, $Y$ and $Z$ be as defined earlier. Then, $10 = |X| = |e_1 \cup e_2| + |Y| = |e_1| + |e_2| - |Z| + |Y|$. By Lemma~\ref{useful}, $|Y| \le 2$ and $|Z| = \theta_X(H) \ge 2$. We first consider the case when $|Z| \ge 3$. By Lemma~\ref{useful} we note that $|Y| \le 1$. Since $H$ has rank at most~$6$, $10 = |e_1| + |e_2| - |Z| + |Y| \le 12 - 3 + 1 = 10$. Since we must have equality throughout this inequality chain, this implies that $|Z| = 3$ and $|Y|=1$. Let $Z = \{z_1,z_2,z_3\}$ and for $i = 1,2,3$, let $g_i$ be the edge in $H[X]$ containing $z_i$ that is different from $e_1$ and $e_2$. Since $H$ is twin-free, we note that $z_i \notin g_j$ for $1 \le i, j \le 3$ and $i \ne j$. Suppose that $g_i$ contains a vertex from $(e_1 \cup e_2) \setminus Z$ for some $i$, $1 \le i \le 3$. Then there are at least three vertices that belong to overlapping edges with $z_i$, implying that $|N_H(z_i)| \le 12$ and the desired result follows. Hence we may assume that no vertex from $g_i$ belongs to $(e_1 \cup e_2) \setminus Z$ for $i=1,2,3$. Since $X$ is a clique, we note that $y \in g_i$ for $i=1,2,3$. However this implies that $y$ is not adjacent to any vertex in $(e_1 \cup e_2) \setminus Z$, a contradiction. Therefore, $|Z|=2$. As before, let $Z = \{z_1,z_2\}$ and for $i = 1,2$, let $g_i$ be the edge in $H[X]$ containing $z_i$ that is different from $e_1$ and $e_2$. Let $W = (e_1 \cup e_2) \setminus Z$. Then, $10 = |X| = |W| + |Y| + |Z|$, which as $|Z|=2$ and $0 \le |Y| \le 2$ implies that $6 \le |W| \le 8$. % If $|g_1 \cap W| \ge 2$, then $|N_H(z_1)| \le 15 - 3 = 12$, and we are done. Hence we may assume that $|g_1 \cap W| \le 1$. Analogously, we may assume that $|g_2 \cap W| \le 1$. Let $W'$ be the vertices in $W$ not covered by $g_1 \cup g_2$. Let $W_1' = W' \cap e_1$ and let $W_2' = W' \cap e_2$, and so $|W'| = |W_1'| + |W_2'|$. Suppose that $|Y| = 2$ and let $Y = \{y_1,y_2\}$. Then, $|W| = 6$. Since $|g_1 \cap W| \le 1$ and $|g_2 \cap W| \le 1$, we note that $|W'| \ge 4$. For $i = 1,2$, let $f_i$ be the edge containing $y_i$ that is different from $g_1$ and $g_2$. Since $X$ is a clique, we have that $W' \subset f_i$ for $i = 1,2$. On the one hand, if $f_1=f_2$, then $\{y_1,y_2\}$ are twins. On the other hand, if $f_1 \ne f_2$, then $\theta_X(H) \ge |f_1 \cap f_2 \cap W'| \ge |W'| \ge 4$. Both cases produce a contradiction. Hence, $|Y| \le 1$. Suppose that $|Y| = 1$ and let $Y = \{y\}$. Then, $|W| = 7$. Since $|g_1 \cap W| \le 1$ and $|g_2 \cap W| \le 1$, we note that $|W'| \ge 5$. Let $g_3$ be the edge of $H[X]$ containing $y$ that is different from $g_1$ and $g_2$. Since $X$ is a clique, we have that $W' \subset g_3$. Renaming $z_1$ and $z_2$ if necessary, we may assume that $|W_1'| \ge |W_2'|$, implying that $\theta_X(H) \ge |e_1 \cap g_3| \ge |W_1'| \ge 3$, a contradiction. Hence, $Y = \emptyset$. Since $|Y| = 0$, we have that $X = e_1 \cup e_2$. Further since $H$ has rank at most~$6$, this implies that $|e_1| = |e_2| = 6$. For $i = 1,2$, let $e_i' = e_i \setminus Z$, and so $|e_i'| = 4$. Let $v$ be an arbitrary vertex in $X \setminus Z$. Renaming $z_1$ and $z_2$ if necessary, we may assume that $v \in e_1'$. Let $e_v'$ and $e_v''$ be the two edges in $H[X]$ different from $e_1$ that contain $v$. Since $X$ is a clique, the vertex $v$ is adjacent to every vertex in $e_2$. If $|e_v' \cap e_2'| \le 1$, then $|e_v'' \cap e_2'| \ge 3$, implying that $\theta_X(H) \ge |e_v'' \cap e_2| \ge 3$, a contradiction. Hence, $|e_v' \cap e_2'| \ge 2$. If $|e_v' \cap e_2'| > 2$, then $\theta_X(H) \ge 3$, a contradiction. Hence, $|e_v' \cap e_2'| = 2$. Analogously, $|e_v'' \cap e_2'| = 2$. Since $v$ is adjacent to every vertex in $e_2$, we note that $(e_v' \cap e_2') \cap (e_v'' \cap e_2') = \emptyset$. This is true for every vertex $v \in X \setminus Z$. Hence every edge in $H[X]$ different from $e_1$ and $e_2$ has size~$4$ in $H[X]$ and contains two vertices in $e_1'$ and two vertices in $e_2'$. Let $e_1' = \{a_1,b_1,c_1,d_1\}$ and let $e_2' = \{a_2,b_2,c_2,d_2\}$. Let $h_1$ be an arbitrary edge in $E(H[X]) \setminus \{e_1,e_2\}$. Renaming vertices if necessary, we may assume that $h_1 = \{a_1,b_1,a_2,b_2\}$. Let $h_2$ and $h_3$ be the edges of $H[X]$ containing $a_1$ and $b_1$, respectively, that are different from $e_1$ and $h_1$. Then, $\{a_1,c_2,d_2\} \subset h_2$ and $\{b_1,c_2,d_2\} \subset h_3$. If $h_2 = h_3$, then $a_1$ and $b_1$ are twins in $H$. If $h_2 \ne h_3$, then $c_2$ and $d_2$ are twins in $H$. In both cases we contradict the fact that $H$ is twin-free. \end{proof} \begin{lemma} If $H$ is a $3$-regular hypergraph of rank at most~$6$ and $X$ is a $9$-clique in $H$, then there exists a vertex $x \in X$ with $|N(x)| \le 13$. \label{clique9} \end{lemma} \begin{proof} Let $X$ be a $9$-clique in $H$. If there are two twins in $H[X]$, then each of them have degree at most~$13$ and we are done. Hence we may assume that there are no twins in $H[X]$. For each edge, $f$, in $H$ containing some vertex $y$ we note that there are at most five vertices in $f \setminus \{y\}$ since $H$ has rank at most~$6$. Define a graph $G_X$ with vertex set $X$ and with an edge between $x,x' \in X$ if and only if $\{x,x'\}$ is a subset of two distinct edges in $H$. Thus every neighbor, $x'$, of a vertex $x \in X$ belongs to two edges of $H$ that contain both $x$ and $x'$. This implies that $|N_H(x)| \le 3 \times 5 - d_{G_X}(x)$. Thus if $d_{G_X}(x) \ge 2$, then $|N_H(x)| \le 13$, and we are done. Therefore we may assume that $d_{G_X}(x) \le 1$ for all $x \in X$. Since $|X|=9$ is odd, this implies that some vertex $x \in X$ is an isolated vertex in $G_X$. Let $f_1,f_2,f_3$ be the three edges in $H[X]$ containing $x$. Suppose that $|f_1|=6$. Let $v \in X \setminus f_1$. Renaming the edges $f_2$ and $f_3$, if necessary, we may assume that $v \in f_2$. Since $X$ is a clique, the vertex $v$ is adjacent to all five vertices in $f_1 \setminus \{x\}$. Hence one of the two edges different from $f_2$ that contain $v$ must intersect $f_1 \setminus \{x\}$ in at least three vertices. But this implies that $d_{G_X}(w) \ge 2$ for some $w \in f_1$, a contradiction. Therefore, $|f_1| \ne 6$. Analogously, $|f_2| \ne 6$ and $|f_3| \ne 6$. Suppose that $|f_1| = 4$. Let $U = X \setminus f_1$ and note that $|U| = 5$. Let $u \in U$. %Renaming $f_2$ and $f_3$, if necessary, we may assume that $u \in f_2$. Since $X$ is a clique, $u$ is adjacent to all three vertices in $f_1 \setminus \{x\}$. Hence one of the two edges in $H[X]$ containing $u$ that is different from $f_2$ and $f_3$ contains at least two vertices in $f_1 \setminus \{x\}$. Let $g_u$ be such an edge of $H[X]$ that contains~$u$. If the five such edges, $g_u$, for all $u \in U$ are identical, then $|g_u| \ge |U| + 2 = 7$, a contradicting the rank of $H$. Therefore there exist two distinct vertices $u$ and $u'$ in $U$ such that $g_u \ne g_{u'}$. Since both $g_u$ and $g_{u'}$ contain at least two vertices in $f_1 \setminus \{x\}$, and since $|f_1 \setminus \{x\}| = 3$, there exists some vertex in $f_1 \setminus \{x\}$ that belongs to both $g_u$ and $g_{u'}$. If $|g_u \cap g_{u'} \cap f_1| \ge 2$, then there exists two twins in $H[X]$, a contradiction. Therefore, $g_u \cap g_{u'} \cap f_1 = \{w\}$ for some vertex $w \in f_1 \setminus \{x\}$. But then $f_1 \setminus \{x,w\} \subseteq N_{G_X}(w)$, implying that $d_{G_X}(w) \ge 2$, a contradiction. Therefore, $|f_1| \ne 4$. Analogously, $|f_2| \ne 4$ and $|f_3| \ne 4$. Renaming the edges if necessary, we may assume that $|f_1| \ge |f_2| \ge |f_3|$. If $|f_1| \le 3$, then $|X| \le 7$, a contradiction. Hence, $|f_1| \ge 4$. However as shown earlier, $|f_1| \ne 4$ and $|f_1| \ne 6$. Therefore, $|f_1|=5$ and $|f_2| \ge 3$. Let $f_1' = f_1 \setminus \{x\}$ and note that $|f_1'| = 4$. Further, let $Q=\{q_1,q_2,q_3,q_4\}= X \setminus f_1$. Consider the vertex $q_i \in Q$ where $1 \le i \le 4$. Since $X$ is a clique, $q_i$ is adjacent to all four vertices in $f_1'$. Further since no two edges of $H$ intersect in more than two vertices, this implies that there exists two edges $r_i$ and $r_i'$ containing $q_i$, such that $|r_i \cap f_1'| = |r_i' \cap f_1'|=2$ and $r_i \cap r_i \cap f_1' = \emptyset$. Let there be $j$ distinct edges in \[ E^* = \bigcup_{i = 1}^4 \{r_i,r_i'\}. \] If $j=2$, then since $|f_2| \ge 3$ there are two twins in $f_2 \setminus \{x\}$, a contradiction. Hence, $j \ge 3$. If two distinct edges in $E^*$ intersect in the same set of two vertices in $f_1'$, then there are two twins in $f_1$, a contradiction. Hence every two distinct edges in $E^*$ have a different intersection in $f_1'$. Since $j \ge 3$, there will therefore be at least three edges with both ends in $f_1'$. This implies that $d_{G_X}(w) \ge 2$ for some $w \in f_1'$, a contradiction. \end{proof} \begin{lemma} If $H$ is a $3$-regular hypergraph of rank at most~$6$ and $X$ is a $8$-clique in $H$, then there exists a vertex $x \in X$ with $|N(x)| \le 14$. \label{clique8} \end{lemma} \begin{proof} Let $X$ be a $8$-clique in $H$. By Lemma~\ref{useful}(a), $\theta_X(H) \ge 2$. Let $e_1$ and $e_2$ be two overlapping edges in $H[X]$ and let $x \in e_1 \cap e_2$. Then, $|N(x)| \le 14$. \end{proof} \medskip We are now in a position to prove Theorem~\ref{main2}. Recall its statement. \noindent \textbf{Theorem~\ref{main2}}. \emph{If $H$ is a twin-free $3$-regular hypergraph of order~$n$ and rank at most~$6$, then $\alpha(H) \ge 2n/23$.} \medskip %\noindent \textbf{Proof.} .... \begin{proof} Let $G$ be the graph with vertex set $V(G)=V(H)$ and where two vertices are adjacent in $G$ if and only if they are adjacent in $H$. Clearly, $\alpha(G)=\alpha(H)$. Since $H$ is $3$-regular of rank at most~$6$, we note that $\Delta(G) \le 15$. Let $p=23$. If $X$ is a clique of size at most~$7$ in $G$, then for each vertex $x \in X$ we have $d_G(x) = |N_H(x)| \le 15 < p-|X|$. If $X$ is a clique of size~$8$ in $G$ (and therefore in $H$), there exists an $x \in X$, such that $d_G(x) = |N_H(x)| < 15 = p-|X|$, by Lemma~\ref{clique8}. If $X$ is a clique of size~$9$ in $G$ (and therefore in $H$) there exists an $x \in X$, such that $d_G(x) = |N_H(x)| < 14 = p-|X|$, by Lemma~\ref{clique9}. If $X$ is a clique of size $10$ in $G$ (and therefore in $H$) there exists an $x \in X$, such that $d_G(x) = |N_H(x)| < 13 = p-|X|$, by Lemma~\ref{clique10}. Furthermore there is no clique in $G$ (or $H$) of size greater than $10$ by Lemma~\ref{clique}. Therefore condition (A) holds in Theorem~\ref{main1}, implying that $\alpha(H) = \alpha(G) \ge 2|V(G)|/p = 2|V(H)|/23 = 2n/23$, by Theorem~\ref{main1}. \end{proof} \medskip We conjecture that the following holds. \begin{conjecture} \label{conj1} If $H$ is a twin-free $3$-regular hypergraph of order~$n$ and rank at most~$6$, then $\alpha(H) \ge n/10$. \end{conjecture} We remark that if Conjecture~\ref{conj1} is true, then the bound is tight due to the following example. Let $H_{10}$ be the $6$-uniform hypergraph with five edges, $e_1,e_2,e_3,e_4,e_5$, and ten vertices defined by $V(H_{10})= \{ u_{i,j,k} \; | \; 1 \le i < j < k \le 5\}$, where the vertex $u_{i,j,k}$ belongs to edges $e_i$, $e_j$ and $e_k$. Then, $H_{10}$ is $3$-regular and $6$-uniform. Furthermore, $H_{10}$ is twin-free as different vertices belong to different sets of edges. Further, for distinct vertices $u_{i,j,k}$ and $u_{i',j',k'}$ in $H_{10}$, we note that $\{i,j,k\} \cap \{i',j',k'\} \ne \emptyset$ as all indices cannot be distinct since they are between $1$ and $5$, implying that $u_{i,j,k}$ and $u_{i',j',k'}$ are adjacent. Hence, $\alpha(H_{10}) = 1 = n/10$, where $n = n(H_{10})$. Therefore, $H_{10}$ would show that Conjecture~\ref{conj1} would be best possible. \section{Transversals in $6$-uniform hypergraphs} Chv\'{a}tal and McDiarmid~\cite{ChMc} established the following upper bound on the transversal number of a uniform hypergraph in terms of its order and size. \begin{unnumbered}{Chv\'{a}tal-McDiarmid Theorem.} For $k \ge 2$, if $H$ is a $k$-uniform hypergraph of order~$n$ and size~$m$, then \[ \tau(H)\le \frac{n + \left\lfloor \frac k2\right\rfloor m}{\left\lfloor \frac{3k}2\right\rfloor}. \] \end{unnumbered} Let $n_i(H)$ denote the number of vertices in $H$ of degree~$i$. As a consequence of the Chv\'{a}tal-McDiarmid Theorem, we have the following two results. %In \cite{ChMc} the following result is proved. %\begin{theorem}{\rm (\cite{ChMc})} \label{ChMcThm} %If $H$ is a $r$-uniform hypergraph of order $n$ and size $m$, then $\tau(H) \le (\lfloor r/2 \rfloor m + n)/\lfloor 3r/2 \rfloor$. %\end{theorem} \begin{corollary} \label{ChMcCor2} If $H$ is a $6$-uniform hypergraph with $\Delta(H) \le 3$, then \[ 18\tau(H) \le 3n_1(H) + 4n_2(H) + 5n_3(H).\] \end{corollary} \begin{proof} Let $H$ be a $6$-uniform hypergraph of order~$n$ and size~$m$ satisfying $\Delta(H) \le 3$. For notational simplicity, let $n_i=n_i(H)$ for $i\in\{1,2,3\}$. Applying the Chv\'{a}tal-McDiarmid Theorem to the hypergraph $H$, we have that \[ \tau(H) \le \frac{n + 3m}{9} = \frac{2n+6m}{18} = \frac{2(n_1+n_2+n_3) + (n_1+2n_2+3n_3)}{18} = \frac{3n_1+4n_2+5n_3}{18}, \] \noindent or, equivalently, $18\tau(H) \le 3n_1(H) + 4n_2(H)+5n_3$. \end{proof} \medskip \begin{corollary} \label{ChMcCor1} If $H$ is a $3$-regular $6$-uniform hypergraph of order $n$, then $\tau(H) \le 5n/18$. %\approx 0.277778 \, n$. \end{corollary} %We remark that $5/18 \approx 0.277778$. Our aim in this section is to lower the best known upper bound on the transversal number of a $3$-regular $6$-uniform hypergraph of order $n$ from $5n/18 \approx 0.27777777 \, n$ (see Corollary~\ref{ChMcCor1}) to $37n/138 \approx 0.268115942 \, n$. In order to state our result, let \[ c_1 = \frac{1}{6}, \hspace*{0.5cm} c_2 = \frac{2}{9}, \hspace*{0.3cm} \mbox{and} \hspace*{0.3cm} c_3 = \frac{37}{138}. \] We first prove the following result on $6$-uniform hypergraphs. We remark that if we allow edges of size less than~$6$, then the result of Theorem~\ref{main3} is not true anymore. For example, $3$-regular $3$-uniform hypergraphs on $n$ vertices may have transversal number~$n/2$ (see, \cite{HeYe08}). \begin{theorem} \label{main3} If $H$ is a $6$-uniform hypergraph with $\Delta(H) \le 3$, %maximum degree at most three, % then \[ \tau(H) \le c_1 n_1(H) + c_2 n_2(H) + c_3 n_3(H).\] \end{theorem} \begin{proof} We proceed by induction on the order of a $6$-uniform hypergraph $H$ satisfying $\Delta(H) \le 3$. For a hypergraph $H'$ with $\Delta(H') \le 3$, let \[ \theta(H')= c_1 n_1(H') + c_2 n_2(H') + c_3 n_3(H'). \] Hence we wish to show that $\tau(H) \le \theta(H)$. If $m(H) = 0$, then $\tau(H) = 0$ and the result is immediate. Hence we may assume that $m(H) \ge 1$, implying that $|V(H)| \ge 6$. If $|V(H)| = 6$, then $\tau(H) = 1 \le \theta(H)$. This establishes the base cases when $|V(H)| \le 6$. Let $H$ be a $6$-uniform hypergraph such that $\Delta(H) \le 3$ and assume the theorem holds for all $6$-uniform hypergraphs $H'$ satisfying $\Delta(H') \le 3$ and $n(H') < n(H)$. If $\Delta(H) \le 2$, then $n_3(H) = 0$ and the theorem holds by Corollary~\ref{ChMcCor2} of the Chv\'{a}tal-McDiarmid Theorem. Hence we may assume that $\Delta(H) = 3$. We consider two cases, depending on whether $H$ has twins of degree~$3$ and or not. Suppose first that $H$ contains two twins, $x_1$ and $x_2$, of degree~$3$. Let $X = \{x_1,x_2\}$ and let $H' = H - \{x_1,x_2\}$. Thus, $H'$ is obtained from $H$ by removing the vertices $X$ from $H$ removing the three hyperedges that intersect $X$, and removing all resulting isolated vertices, if any. Let $T'$ be a minimum transversal in $H'$. Then, $T = T' \cup \{x_1\}$ is a transversal in $H$, and so $\tau(H) \le |T| = |T'| + 1 = \tau(H') + 1$. We note that by removing the three edges that contain $X$, the degrees of $x_1$ and $x_2$ drop from~$3$ to zero. Further, if some vertex $v \notin X$ belongs to $i$ of the deleted edges its degree drops to $d_H(v) - i$ in $H'$, implying that the sum of the degrees of vertices not in $X$ decrease by~$12$ in $H'$ due to the $6$-uniformity of $H$. If the degree of a vertex drops from~$1$ to~$0$ in $H'$, then it decreases $\theta(H)$ by~$c_1$. If its degree drops from~$2$ to~$1$ in $H'$, then it decreases $\theta(H)$ by~$c_2 - c_1$, while if its drops from~$3$ to~$2$ in $H'$, then it decreases $\theta(H)$ by~$c_3 - c_2$. Since $c_1 \ge c_2-c_1 \ge c_3-c_2$, we therefore have that whenever the degree of a vertex drops by~$1$ in $H'$, then it decreases $\theta(H)$ by at least~$c_3 - c_2$. Therefore, \[ \theta(H') \le \theta(H) - 2c_3 - 12(c_3-c_2) = \theta(H) + 12 c_2 - 14 c_3 < \theta(H) - 1, \] implying that \[ \tau(H) \le |T| = |T'|+1 \le \theta(H')+1 < \theta(H). \] \noindent Hence if $H$ contains two twins, $x_1$ and $x_2$, of degree~$3$, then $\tau(H) < \theta(H)$. We may therefore assume $H$ has no twins of degree~$3$, for otherwise the desired result holds. Recall that by our earlier assumption, $\Delta(H) = 3$. Let $R$ contain all vertices in $H$ of degree~$3$. Then, $H[R]$ is a $3$-regular hypergraph of rank at most six and with no twins. By Theorem~\ref{main2} there exists a strongly independent set, $I$, in $H[R]$ of size at least $2|R|/23$. Let $H' = H - I$ and let $E^*=\{e_1^*,e_2^*,\ldots,e_{3|I|}^*\}$ be the set of $3|I|$ edges containing vertices from $I$. As observed earlier, when we delete an edge $e$ from a $6$-uniform hypergraph $H$ with maximum degree at most~$3$ and if $v \in e$, then $\theta(H)$ drops by $c_3-c_2$ if $d_H(v) = 3$, $\theta(H)$ drops by $c_2-c_1$ if $d_H(v) = 2$, and $\theta(H)$ drops by $c_1$ if $d_H(v) = 1$. Further, $c_1 \ge c_2-c_1 \ge c_3-c_2$. Thinking of $H'$ as being obtained from $H$ by removing the edges $e_1^*$, $e_2^*$, $e_3^*$, \ldots, $e_{3|I|}^*$ in that order, we note that exactly~$|R|$ times we drop $\theta(H)$ by~$c_3-c_2$, once for each vertex in $R$ (noting that each vertex in $R$ is contained in at least one edge in $E^*$). Further, at least $|I|$ times we drop $\theta(H)$ by $c_1$ since all edges are removed from the vertices in the independent set $I$. The total sum of the degrees of vertices decrease by~$6|E^*|$ in $H'$ due to the $6$-uniformity of $H$. We therefore obtain the following. \begin{center} $\begin{array}{rcl} \theta(H') + |I| & \le & |I| + \theta(H) - (c_3-c_2)|R| - c_1|I| - (c_2-c_1)(6|E^*|-|R|-|I|) \\ & = & |I|+ \theta(H) - (c_3-c_2)|R| - c_1|I| - (c_2-c_1)(18|I|-|R|-|I|) \\ & = & \theta(H) - (c_3-c_2-c_2+c_1)|R| - (c_1 + 17c_2 -17c_1-1)|I| \\ & = & \theta(H) - (c_3-2c_2+c_1)|R| - (17c_2 - 16c_1 -1)|I| \\ & \le & \theta(H) - (c_3-2c_2+c_1)|R| - 2(17c_2 - 16c_1-1)|R|/23 \\ & = & \theta(H) - (23c_3 - 46c_2 + 23c_1 + 34c_2 - 32c_1 -2)|R|/23 \\ & = & \theta(H) - (23c_3 - 12c_2 - 9c_1 - 2)|R|/23 \\ & = & \theta(H). \\ \end{array}$ \end{center} Applying the inductive hypothesis to $H'$, we have that $\tau(H') \le \theta(H')$. Every transversal in $H'$ can be extended to a transversal in $H$ by adding to it the set $I$, implying that \[ \tau(H) \le \tau(H') + |I| \le \theta(H') + |I| \le \theta(H), \] \noindent which completes the proof. \end{proof} \medskip As a consequence of Theorem~\ref{main3}, we have the following result for $6$-uniform hypergraphs. \begin{corollary} If $H$ is a $3$-regular $6$-uniform hypergraph of order $n$, then $\tau(H) \le 37n/138 \approx 0.268115942 \, n$. \label{cor6unif} \end{corollary} \begin{proof} If $H$ is a $3$-regular $6$-uniform hypergraph of order $n$, then by Theorem~\ref{main3} we have that $\tau(H) \le c_1n_1(H) + c_2n_2(H) + c_3n_3(H) = 0+0+37n/138$. \end{proof} \medskip We remark that Corollary~\ref{cor6unif} gives support for the following long-standing conjecture due to Tuza and Vestergaard~\cite{TuVe02}, in that it lowers the best known upper bound on the transversal number of a $3$-regular $6$-uniform hypergraph of order $n$ from $5n/18$ to $37n/138$. \begin{unnumbered}{Tuza-Vestergaard Conjecture.} If $H$ is a $3$-regular $6$-uniform hypergraph of order $n$, then $\tau(H) \le n/4 = 0.25n$. \end{unnumbered} \section*{Acknowledgements} Research of Michael A. Henning supported in part by the South African National Research Foundation and the University of Johannesburg. Christian L\"{o}wenstein is indebted to the Baden-W\"{u}rttemberg Stiftung for the financial support of this research project by the Eliteprogramme for Postdocs. \begin{thebibliography}{10} \bibitem{ChMc} V. Chv\'atal and C. McDiarmid. \newblock Small transversals in hypergraphs. \newblock \textit{Combinatorica}, 12:19--26, 1992. \bibitem{CoHeSl79} E. J. Cockayne, S. T. Hedetniemi and P. J. Slater. \newblock Matchings and transversals in hypergraphs, domination and independence-in trees. \newblock \textit{J. Combin. Theory B}, 27:78--80, 1979. \bibitem{Fa78} S. Fajtlowicz. \newblock On the size of independent sets in graphs. \newblock \textit{Congressus Numerantium}, 21:269--274, 1978. \bibitem{Fa84} S. Fajtlowicz. \newblock Independence, clique size and maximum degree. \newblock \textit{Combinatorica}, 4:35--38, 1984. \bibitem{HeYe08} M. A. Henning and A. Yeo. \newblock Hypergraphs with large transversal number and with edge sizes at least three. \newblock \textit{J. Graph Theory}, 59:326--348, 2008. \bibitem{LaCh90} F. C. Lai and G. J. Chang. \newblock An upper bound for the transversal numbers of 4-uniform hypergraphs. \newblock \textit{J. Combin. Theory Ser. B}, 50:129–-133, 1990. \bibitem{ThYe07} S. Thomass\'{e} and A. Yeo. \newblock Total domination of graphs and small transversals of hypergraphs. \newblock \textit{Combinatorica}, 27:473--487, 2007. \bibitem{TuVe02} Zs. Tuza and P. H. Vestergaard. \newblock Domination in partitioned graphs. \newblock \textit{Discussiones Math. Graph Theory}, 22:199--210, 2002. \end{thebibliography} \end{document}