Journal
GRAPHS AND COMBINATORICS
Volume 38, Issue 4, Pages -Publisher
SPRINGER JAPAN KK
DOI: 10.1007/s00373-022-02499-7
Keywords
Odd graph; Planar graph; Induced subgraph; Girth
Categories
Funding
- NSFC [12001106]
- National Natural Science Foundation of Fujian Province [2021J05128]
- Foundation of Fuzhou University [GXRC20059]
Ask authors/readers for more resources
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.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available