Written on the Wall II - Conjecture 58

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

Counterexample

The conjecture is false. A counterexample is given by taking $K_{3,3}$ (with bipartition $\{0,1,2\}$, $\{3,4,5\}$) and $K_{73}$ (on vertices $\{6,\ldots,78\}$), then adding edges between vertex $0$ and every vertex of $K_{73}$.

This graph $G$ has $n = 79$ vertices and satisfies:

• $b(G) \ge 7$: the set $\{0,1,2,3,4,5,6\}$ induces a bipartite subgraph
• $f(G) \le 6$: the largest induced forest has at most 6 vertices
• $l_{\mathrm{avg}}(G) = 92/79$
• $\lceil b(G) / l_{\mathrm{avg}}(G) \rceil \ge 7 > 6 \ge f(G)$

theorem WrittenOnTheWallII.GraphConjecture58.conjecture58 : False ↔ ∀ (α : Type) [inst : Fintype α] [DecidableEq α] [Nontrivial α] (G : SimpleGraph α) [DecidableRel G.Adj], G.Connected → ⌈G.b / G.l_avg⌉₊ ≤ G.largestInducedForestSize

WOWII Conjecture 58

For a connected graph G, the size f(G) of a largest induced forest satisfies f(G) ≥ ceil( b(G) / average l(v) ) where b(G) is the largest induced bipartite subgraph and l(v) is the independence number of G.neighborSet v.

This conjecture is false. A counterexample is the graph described in the module docstring above: a $K_{3,3}$ joined to a $K_{73}$ via vertex $0$, giving $\lceil b/l_{\mathrm{avg}} \rceil \ge 7 > 6 \ge f(G)$.

The counterexample has been found by Moritz Firsching and Goran Žužić using an experimental pipeline.