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

作者：Henning Michael A^*; Loewenstein Christian; Southey Justin; Yeo Anders

来源：Electronic Journal of Combinatorics, 2014, 21(1): P1.38.

• independence
• clique
• transversal

The independence number of a graph C, denoted a(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 T (H) <= n/4.

• 出版日期2014-2-21