A new lower bound on the independence number of a graph and applications
type: Item
instance of: scholarly article
title: A new lower bound on the independence number of a graph and applications
zbMATH Open document ID: 1300.05226
author: Michael A. Henning
author: Christian Löwenstein
author: Justin Southey
author: A. Yeo
published in: The Electronic Journal of Combinatorics
publication date: 2014-09-04T00:00:00Z
full work available at URL: v21i1p38
review text: 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\).
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C07
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 6340136
zbMATH Keywords: maximum clique size
MaRDI profile type: Publication
cites work: Small transversals in hypergraphs
cites work: Matchings and transversals in hypergraphs, domination and independence in trees
cites work: Q3872499
cites work: Independence, clique size and maximum degree
cites work: Hypergraphs with large transversal number and with edge sizes at least 3
cites work: An upper bound for the transversal numbers of 4-uniform hypergraphs
cites work: Total domination of graphs and small transversals of hypergraphs
cites work: Domination in partitioned graphs
description: scientific article; zbMATH DE number 6340136