Indexed by:
Abstract:
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 χ) - 1 for graphs with chromatic number χ≥ 2 and conjectured that c≥ χ- 1. Partial tight bounds of c are also established by various authors for graphs such as trees, graphs with maximum degree 3 or K4-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. © 2022, The Author(s), under exclusive licence to Springer Japan KK, part of Springer Nature.
Keyword:
Reprint 's Address:
Email:
Source :
Graphs and Combinatorics
ISSN: 0911-0119
Year: 2022
Issue: 4
Volume: 38
0 . 7
JCR@2022
0 . 6 0 0
JCR@2023
ESI HC Threshold:24
JCR Journal Grade:3
CAS Journal Grade:4
Cited Count:
SCOPUS Cited Count: 1
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 1
Affiliated Colleges: