Lower bounds on the independence number of a graph in terms of degrees
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909038735785984 |
|---|---|
| author | Harant, Jochen Schiermeyer, Ingo |
| author_facet | Harant, Jochen Schiermeyer, Ingo |
| contents | Given an integer $Δ\ge 3$, let ${\cal G}_{Δ}$ be the set of connected graphs $G\neq K_{Δ+1}$ with maximum degree $Δ$ and, for $i=1,\cdots, Δ$, let $V_i(G)$ be the set of vertices of $G$ of degree $i$. \\ We prove that $\sum\limits_{i=1}^Δc_i|V_i(G)|$ is a lower bound on the independence number $α(G)$ of $G\in {\cal G}_Δ$, where $c_Δ=\frac{1}Δ$ and $ic_{i}=1-c_{i+1}$ for $i=1,\cdots,Δ-1$. Moreover, if $\varepsilon >0$ and $j\in \{1,\cdots, Δ\}$, then the inequality $α(G)\ge \varepsilon|V_j(G)|+\sum\limits_{i=1}^Δc_i|V_i(G)|$ does not hold for infinitely many graphs $G\in {\cal G}_Δ$. We also show that an independent set $I\subset V(G)$ of $G\in {\cal G}_Δ$ such that $|I|\ge \sum\limits_{i=1}^Δc_i|V_i(G)|$ can be found in polynomial time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_16326 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Lower bounds on the independence number of a graph in terms of degrees Harant, Jochen Schiermeyer, Ingo Combinatorics 05C35, 05C69 Given an integer $Δ\ge 3$, let ${\cal G}_{Δ}$ be the set of connected graphs $G\neq K_{Δ+1}$ with maximum degree $Δ$ and, for $i=1,\cdots, Δ$, let $V_i(G)$ be the set of vertices of $G$ of degree $i$. \\ We prove that $\sum\limits_{i=1}^Δc_i|V_i(G)|$ is a lower bound on the independence number $α(G)$ of $G\in {\cal G}_Δ$, where $c_Δ=\frac{1}Δ$ and $ic_{i}=1-c_{i+1}$ for $i=1,\cdots,Δ-1$. Moreover, if $\varepsilon >0$ and $j\in \{1,\cdots, Δ\}$, then the inequality $α(G)\ge \varepsilon|V_j(G)|+\sum\limits_{i=1}^Δc_i|V_i(G)|$ does not hold for infinitely many graphs $G\in {\cal G}_Δ$. We also show that an independent set $I\subset V(G)$ of $G\in {\cal G}_Δ$ such that $|I|\ge \sum\limits_{i=1}^Δc_i|V_i(G)|$ can be found in polynomial time. |
| title | Lower bounds on the independence number of a graph in terms of degrees |
| topic | Combinatorics 05C35, 05C69 |
| url | https://arxiv.org/abs/2512.16326 |