The independence number of graphs with large odd girth
From MaRDI portal
(Redirected from Publication:1346728)
Summary: Let \(G\) be an \(r\)-regular graph of order \(n\) and independence number \(\alpha(G)\). We show that if \(G\) has odd girth \(2k+ 3\) then \(\alpha(G)\geq n^{1-1/k} r^{1/k}\). We also prove similar results for graphs which are not regular. Using these results we improve on the lower bound of Monien and Speckenmeyer, for the independence number of a graph of order \(n\) and odd girth \(2k+ 3\).
Recommendations
Cited in
(11)- The independence number of dense graphs with large odd girth
- Regular independent sets
- Lower bounds for on-line graph colorings
- Parameterized algorithms for the independent set problem in some hereditary graph classes
- Independence, odd girth, and average degree
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- scientific article; zbMATH DE number 4049676 (Why is no real title available?)
- Lower bounds on the independence number of certain graphs of odd girth at least seven
- On the independence number of regular graphs of matrix rings
- On finding augmenting graphs
- Online coloring graphs with high girth and high odd girth
This page was built for publication: The independence number of graphs with large odd girth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1346728)
