Written on the Wall II - Conjecture 59

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

theorem WrittenOnTheWallII.GraphConjecture59.conjecture59 {α : Type u_1} [Fintype α] [DecidableEq α] [Nontrivial α] (G : SimpleGraph α) [DecidableRel G.Adj] (h : G.Connected) : ↑⌈√(↑G.residue * G.b)⌉ ≤ ↑G.largestInducedForestSize

WOWII Conjecture 59

For a simple connected graph $G$, the size $f(G)$ of a largest induced forest satisfies $f(G) \ge \lceil \sqrt{\mathrm{residue}(G) \cdot b(G)} \rceil$, where $\mathrm{residue}(G)$ is the Havel-Hakimi residue (the number of zeros remaining after applying the Havel-Hakimi algorithm to the degree sequence until termination) 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.