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

Michael A. Henning, Justin Southey, Christian Löwenstein, Anders Yeo

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

The independence number of a graph G, denoted α(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.

Original languageEnglish
JournalElectronic Journal of Combinatorics
Volume21
Issue number1
ISSN1097-1440
DOIs
Publication statusPublished - 2014
Externally publishedYes

Keywords

  • Clique
  • Independence
  • Transversal

Fingerprint

Dive into the research topics of 'A new lower bound on the independence number of a graph and applications'. Together they form a unique fingerprint.

Cite this