
Michael A. Henning

Christian LĂ¶wenstein

Justin Southey

Anders Yeo
Keywords:
Graph Theory
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 wellstudied graph parameters. In this paper, we strengthen a result of Fajtlowicz [Combinatorica 4 (1984), 3538] 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), 199210] that if $H$ is a $3$regular $6$uniform hypergraph of order $n$, then $\tau(H) \le n/4$.