A new lower bound on the independence number of a graph and applications (Q405126)

Summary: 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 \textit{S. Fajtlowicz} [Combinatorica 4, 35--38 (1984; Zbl 0576.05025)] 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 \textit{Z. Tuza} and \textit{P. D. Vestergaard} [Discuss. Math., Graph Theory 22, No. 1, 199--210 (2002; Zbl 1016.05057)] that if \(H\) is a \(3\)-regular \(6\)-uniform hypergraph of order \(n\), then \(\tau(H) \leq n/4\).