Written on the Wall II - Conjecture 109

Reference: E. DeLaVina, Written on the Wall II, Conjectures of Graffiti.pc

theorem WrittenOnTheWallII.GraphConjecture109.conjecture109 {α : Type u_1} [Fintype α] [DecidableEq α] [Nontrivial α] (G : SimpleGraph α) [DecidableRel G.Adj] (h : G.Connected) : ↑G.indepNum ≤ ↑⌊(↑G.residue + 2 * G.b) / 3⌋

WOWII Conjecture 109

For a simple connected graph $G$, the independence number $\alpha(G)$ satisfies $\alpha(G) \le \lfloor (\mathrm{residue}(G) + 2 \cdot b(G)) / 3 \rfloor$, where $\mathrm{residue}(G)$ is the Havel-Hakimi residue and $b(G)$ is the size of a largest induced bipartite subgraph.

See: Favaron, Mahéo, Saclé (1991) for the residue; DeLaVina's Graffiti.pc for the conjecture.