论文标题
图形的最大奇数诱导子图有关其色数
Maximum odd induced subgraph of a graph concerning its chromatic number
论文作者
论文摘要
令$ f_ {o}（g）$为$ g $的奇数子图的最大顺序。在1992年，斯科特（Scott）提出了一个猜想，即$ f_ {o}（g）\ geq \ frac {n} {n} {2χ（g）} $对于$ g $ of Order $ n $而不孤立的顶点，其中$χ（g）$是$ g $的$ g $。在本文中，我们表明猜想对于两部分图不是正确的，但对于所有界限图都是正确的。此外，我们还在1997年反驳了贝尔曼，王和沃戈的猜想，该猜想指出$ f_ {o}（g）\ geq 2 \ lfloor \ lfloor \ frac {n} {4} {4} \ rfloor $对于连接的$ g $ of订单$ n $。 Scott的猜想是针对具有至少3个色度的图表开放的。
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)\geq \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)\geq 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.
