期刊
GRAPHS AND COMBINATORICS
卷 38, 期 4, 页码 -出版社
SPRINGER JAPAN KK
DOI: 10.1007/s00373-022-02499-7
关键词
Odd graph; Planar graph; Induced subgraph; Girth
类别
资金
- NSFC [12001106]
- National Natural Science Foundation of Fujian Province [2021J05128]
- Foundation of Fuzhou University [GXRC20059]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据