2026/07/22 by Dickson Y. B. Annor, Ben Howerton
Mathematics · #math.CO
arxiv created 2026/07/29 · arxiv updated 2026/07/30
Let G be a graph with chromatic number χ(G), clique number ω(G) and zero forcing number Z(G). We establish new lower bounds on Z(G) in terms of induced triangle-free subgraphs. In particular, we show that if a graph G contains an induced triangle-free subgraph H with minimum degree δ(H) ≥ 3, then Z(G)≥δ(H)+1. As consequences, we prove that every triangle-free graph satisfies χ(G)≤max\3,Z(G)\, and we obtain further chromatic bounds for triangle-free graphs with Δ(G)≤δ(G)+1 and for planar graphs.