Maximum odd induced subgraph of a graph concerning its chromatic number

被引:1
作者
Wang, Tao [1 ]
Wu, Baoyindureng [1 ]
机构
[1] Xinjiang Univ, Coll Math & Syst Sci, Urumqi 830046, Xinjiang, Peoples R China
基金
中国国家自然科学基金;
关键词
chromatic number; induced subgraphs; odd subgraphs; TREES;
D O I
10.1002/jgt.23148
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let fo(G) ${f}_{o}(G)$ be the maximum order of an odd induced subgraph of G $G$. In 1992, Scott proposed a conjecture that fo(G)>= n chi(G) ${f}_{o}(G)\ge \frac{n}{\chi (G)}$ for a graph G $G$ of order n $n$ without isolated vertices, where chi(G) $\chi (G)$ is the chromatic number of G $G$. In this paper, we show that the conjecture is not true for bipartite graphs, but is true for all line graphs. In addition, we also disprove a conjecture of Berman, Wang, and Wargo in 1997, which states that fo(G)>= 2n4 ${f}_{o}(G)\ge 2\unicode{x0230A}\frac{n}{4}\unicode{x0230B}$ for a connected graph G $G$ of order n $n$. Scott's conjecture is open for graphs with chromatic number at least 3.
引用
收藏
页码:578 / 596
页数:19
相关论文
共 15 条
[1]   On the Complexity of Finding Large Odd Induced Subgraphs and Odd Colorings [J].
Belmonte, Remy ;
Sau, Ignasi .
ALGORITHMICA, 2021, 83 (08) :2351-2373
[2]  
Berman D.M., 1997, Australas. J. Combin., V15, P81
[3]   All trees contain a large induced subgraph having all degrees 1 (mod k) [J].
Berman, DM ;
Radcliffe, AJ ;
Scott, AD ;
Wang, H ;
Wargo, L .
DISCRETE MATHEMATICS, 1997, 175 (1-3) :35-40
[4]  
Bondy J.A., 2008, Graduate texts in mathematics: Graph theory, VFirst, DOI [DOI 10.1007/978-1-84628-970-5, 10.1007/978-1-84628-970-5]
[5]   ON INDUCED SUBGRAPHS OF TREES, WITH RESTRICTED DEGREES [J].
CARO, Y ;
KRASIKOV, I ;
RODITTY, Y .
DISCRETE MATHEMATICS, 1994, 125 (1-3) :101-106
[6]   ON INDUCED SUBGRAPHS WITH ODD DEGREES [J].
CARO, Y .
DISCRETE MATHEMATICS, 1994, 132 (1-3) :23-28
[7]   Every graph contains a linearly sized induced subgraph with all degrees odd [J].
Ferber, Asaf ;
Krivelevich, Michael .
ADVANCES IN MATHEMATICS, 2022, 406
[8]   Note on Perfect Forests [J].
Gutin, Gregory .
JOURNAL OF GRAPH THEORY, 2016, 82 (03) :233-235
[9]   Odd Induced Subgraphs in Graphs with Treewidth at Most Two [J].
Hou, Xinmin ;
Yu, Lei ;
Li, Jiaao ;
Liu, Boyuan .
GRAPHS AND COMBINATORICS, 2018, 34 (04) :535-544
[10]   How many disjoint 2-edge paths must a cubic graph have? [J].
Kelmans, A ;
Mubayi, D .
JOURNAL OF GRAPH THEORY, 2004, 45 (01) :57-79