## 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 language | English |
---|---|

Journal | Electronic Journal of Combinatorics |

Volume | 21 |

Issue number | 1 |

DOIs | |

Publication status | Published - 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