2025/11/19 by Ai, Jiangdong, Guo, Qiwen, Gutin, Gregory +2
Mathematics · Computer Science · Engineering · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #graph theory and CDMA systems
paper · doi:10.48550/arxiv.2511.15489
A graph is called odd if all of its vertex degrees are odd. A long-standing conjecture asked whether there exists a positive constant c such that every n-vertex graph without isolated vertices contains an odd induced subgraph on at least cn vertices. In 2022, Ferber and Krivelevich resolved this conjecture affirmatively with c=10-4. A natural question is to determine the largest possible constant c. In 1994, Caro remarked that if 2/7 is a valid value for c, then it is the largest possible one. To the best of our knowledge, the bound c≥ 2/7 has not been improved. Previous research has established tight bounds for specific graph classes -- for instance, c = 2/5 for graphs with maximum degree at most 3 and without isolated vertices. In this paper, we prove that c=2/7 is the tight bound for graphs with maximum degree at most 4 and without isolated vertices. Our result provides some support for 2/7 being the largest value of c.