Odd Induced Subgraphs in Planar Graphs with Large Girth

A long-standing conjecture asserts that there is a positive constant c such that every n-vertex graph without isolated vertices contains an induced subgraph with all degrees odd on at least cn vertices. Recently, Ferber and Krivelevich confirmed the conjecture with c >= 10(-4). However, this is far from optimal for special family of graphs. Scott proved that c >= (2 chi)(-1) for graphs with chromatic number chi >= 2 and conjectured that c >= chi(-1). Partial tight bounds of c are also established by various authors for graphs such as trees, graphs with maximum degree 3 or K-4-minor-free graphs. In this paper, we further prove that c >= 2/5 for planar graphs with girth at least 7, and the bound is tight. We also show that c <= 1/3 for general planar graphs and c >= 1/3 for planar graphs with girth at least 6.

Automated summary

This paper explores a long-standing conjecture in graph theory, confirming optimal bounds for certain cases and establishing partial tight bounds of c for different types of graphs.