Maximum odd induced subgraph of a graph concerning its chromatic number

2022/11/20 by Tao Wang, Wang, Tao, Baoyindureng Wu +1 · 3 citations
Mathematics · Computer Science · Engineering · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2211.10895

Abstract

Let f_o(G) be the maximum order of an odd induced subgraph of G. In 1992, Scott proposed a conjecture that f_o(G)≥ \frac n 2χ(G) for a graph G of order n without isolated vertices, where χ(G) is the chromatic number of 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 f_o(G)≥ 2\lfloor\frac n 4\rfloor for a connected graph G of order n. Scott's conjecture is open for a graph with chromatic number at least 3.

Cited by

• Large odd induced subgraphs via odd cuts
• Odd Induced Subgraphs in Graphs of Maximum Degree Four
• Large induced subgraphs with prescribed degree parity

Related

• Odd induced subgraphs in graphs with treewidth at most two
• Odd Induced Subgraphs in Graphs of Maximum Degree Four
• New bounds for odd colourings of graphs
• Odd Chromatic Number of Graph Classes
• The overfull conjecture on graphs of odd order and large minimum degree