The independence number of dense graphs with large odd girth
From MaRDI portal
(Redirected from Publication:1344960)
Summary: Let \(G\) be a graph with \(n\) vertices and odd girth \(2k + 3\). Let the degree of a vertex \(v\) of \(G\) be \(d_ 1 (v)\). Let \(\alpha (G)\) be the independence number of \(G\). Then we show \[ \alpha(G) \geq 2^{-\left( \frac {k-1}{k} \right)} \left[\displaystyle {\sum_{v \in G}}d_ 1 (v)^{\frac{1}{k - 1}} \right]^{(k - 1)/k}. \] This improves and simplifies results proven by Denley.
Recommendations
Cited in
(10)- The independence number of graphs with large odd girth
- The Erdős-Hajnal conjecture for three colors and triangles
- The independence numbers of weighted graphs with forbidden cycles
- Adjacency eigenvalues of graphs without short odd cycles
- Independence, odd girth, and average degree
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Lower bounds for independence numbers of some locally sparse graphs
- The critical window for the classical Ramsey-Turán problem
- The maximum spectral radius of \(\{C_3, C_5\}\)-free graphs of given size
- Lower bounds on the independence number of certain graphs of odd girth at least seven
This page was built for publication: The independence number of dense graphs with large odd girth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1344960)
