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

From MaRDI portal
scientific article
Language Label Description Also known as
English
A new lower bound on the independence number of a graph and applications
scientific article

    Statements

    A new lower bound on the independence number of a graph and applications (English)
    0 references
    0 references
    0 references
    0 references
    4 September 2014
    0 references
    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\).
    0 references
    maximum clique size
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references