1Department of Mathematics University of Johannesburg Auckland Park, 2006 2Institute of Optimization and Operations Research Ulm University, Ulm 89081 3Engineering Systems and Design Singapore University of Technology and Design 20 Dover Drive Singapore, 138682, Singapore and Department of Mathematics University of Johannesburg Auckland Park, 2006 South Africa
The electronic journal of combinatorics, Tome 21 (2014) no. 1
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 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 $\tau(H) \le n/4$.
Michael A. Henning
1
;
Christian Löwenstein
2
;
Justin Southey
1
;
Anders Yeo
3
1
Department of Mathematics
University of Johannesburg
Auckland Park, 2006
2
Institute of Optimization and Operations Research
Ulm University,
Ulm 89081
3
Engineering Systems and Design
Singapore University of Technology and Design
20 Dover Drive Singapore, 138682, Singapore
and
Department of Mathematics
University of Johannesburg
Auckland Park, 2006 South Africa
@article{10_37236_3601,
author = {Michael A. Henning and Christian L\"owenstein and Justin Southey and Anders Yeo},
title = {A new lower bound on the independence number of a graph and applications},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {1},
doi = {10.37236/3601},
zbl = {1300.05226},
url = {http://geodesic.mathdoc.fr/articles/10.37236/3601/}
}
TY - JOUR
AU - Michael A. Henning
AU - Christian Löwenstein
AU - Justin Southey
AU - Anders Yeo
TI - A new lower bound on the independence number of a graph and applications
JO - The electronic journal of combinatorics
PY - 2014
VL - 21
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/3601/
DO - 10.37236/3601
ID - 10_37236_3601
ER -
%0 Journal Article
%A Michael A. Henning
%A Christian Löwenstein
%A Justin Southey
%A Anders Yeo
%T A new lower bound on the independence number of a graph and applications
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/3601/
%R 10.37236/3601
%F 10_37236_3601
Michael A. Henning; Christian Löwenstein; Justin Southey; Anders Yeo. A new lower bound on the independence number of a graph and applications. The electronic journal of combinatorics, Tome 21 (2014) no. 1. doi: 10.37236/3601
