A new lower bound on the independence number of a graph and applications
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\).
- On vertex independence number of uniform hypergraphs
- New results on \(k\)-independence of hypergraphs
- Independence in uniform linear triangle-free hypergraphs
- Bounds on the independence number of a graph in terms of order, size and maximum degree
- A note on the caro-tuza bound on the independence number of uniform hypergraphs
- An upper bound for the transversal numbers of 4-uniform hypergraphs
- Domination in partitioned graphs
- scientific article; zbMATH DE number 3675940 (Why is no real title available?)
- Hypergraphs with large transversal number and with edge sizes at least 3
- Independence, clique size and maximum degree
- Matchings and transversals in hypergraphs, domination and independence in trees
- Small transversals in hypergraphs
- Total domination of graphs and small transversals of hypergraphs
- A lower bound on the independence number of a graph
- A new upper bound on the total domination number in graphs with minimum degree six
- Zero forcing in claw-free cubic graphs
- Transversals and independence in linear hypergraphs with maximum degree two
- Lower bounds for the independence and \(k\)-independence number of graphs using the concept of degenerate degrees
- A lower bound on the independence number of a graph in terms of degrees and local clique sizes
- New Bounds of Induced Acyclic Graphoidal Decomposition Number of a Graph
- scientific article; zbMATH DE number 3989382 (Why is no real title available?)
- Improved lower bounds on k‐independence
- On vertex independence number of uniform hypergraphs
- New lower bounds on independence number in triangle-free graphs in terms of order, maximum degree and girth
- New bounds on the independence number of connected graphs
- An improved lower bound on the independence number of a graph
- Perfect Roman domination in regular graphs
- Bounds on the independence number of a graph in terms of order, size and maximum degree
- A new notion of vertex independence and rank for finite graphs
- New results on \(k\)-independence of graphs
- Packing in regular graphs
- Conjectures of TxGraffiti: independence, domination, and matchings
- A note on Reed's conjecture for triangle-free graphs
- The Tuza–Vestergaard Theorem
- Some bounds on the size of maximum G-free sets in graphs
- Lower bounds on the independence number of certain graphs of odd girth at least seven
- The packing number of cubic graphs
- On independent domination and packing numbers of subcubic graphs
This page was built for publication: A new lower bound on the independence number of a graph and applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q405126)
