• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Rao, M. (Rao, M..) [1] | Hou, J. (Hou, J..) [2] | Zeng, Q. (Zeng, Q..) [3]

Indexed by:

Scopus

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:

Girth; Induced subgraph; Odd graph; Planar graph

Community:

  • [ 1 ] [Rao, M.]Center for Discrete Mathematics, Fuzhou University, Fujian, Fuzhou, 350003, China
  • [ 2 ] [Hou, J.]Center for Discrete Mathematics, Fuzhou University, Fujian, Fuzhou, 350003, China
  • [ 3 ] [Zeng, Q.]Center for Discrete Mathematics, Fuzhou University, Fujian, Fuzhou, 350003, China

Reprint 's Address:

  • [Zeng, Q.]Center for Discrete Mathematics, Fujian, China

Show more details

Related Keywords:

Related Article:

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:

WoS CC 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:

Online/Total:35/10132590
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1