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 journalArticlepeer-review

16 Citations (Scopus)

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
DOIs
Publication statusPublished - 21 Feb 2014

Keywords

  • Clique
  • Independence
  • Transversal

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

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