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 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.
Keyword:
Reprint 's Address:
Version:
Source :
GRAPHS AND COMBINATORICS
ISSN: 0911-0119
Year: 2022
Issue: 4
Volume: 38
0 . 7
JCR@2022
0 . 6 0 0
JCR@2023
ESI Discipline: MATHEMATICS;
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: