论文标题
色度稳定性指数的一些极端结果
Some extremal results on the chromatic-stability index
论文作者
论文摘要
图$ g $的$χ$稳定索引$ {\ rm es}_χ（g）$是其边缘的最小数量，其删除的最小数量会导致图形，其变色数小于$ g $。在本文中，考虑了[欧洲J. \ combin。\ 84（2020）103042]的三个开放问题。构建了示例，该示例表明，$ k $ regular（$ k \ le 5 $）的已知表征$ {\ rm es}_χ（g）= 1 $不扩展到$ k \ ge 6 $。图$ g $带有$χ（g）= 3 $，其中$ {\ rm es}_χ（g）+{\ rm es}_χ（\ overline {g}）= 2 $ holds的表征。在$ {\ rm es}_χ（g）$上以$ {\ rm es} _ $的$ g $ $ g $的必要条件，以$ g $的订单和色度数。事实证明，当$ n \ equiv 2 \ pmod 3 $和$χ（g）= 3 $时，情况就足够了。
The $χ$-stability index ${\rm es}_χ(G)$ of a graph $G$ is the minimum number of its edges whose removal results in a graph with the chromatic number smaller than that of $G$. In this paper three open problems from [European J.\ Combin.\ 84 (2020) 103042] are considered. Examples are constructed which demonstrate that a known characterization of $k$-regular ($k\le 5$) graphs $G$ with ${\rm es}_χ(G) = 1$ does not extend to $k\ge 6$. Graphs $G$ with $χ(G)=3$ for which ${\rm es}_χ(G)+{\rm es}_χ(\overline{G}) = 2$ holds are characterized. Necessary conditions on graphs $G$ which attain a known upper bound on ${\rm es}_χ(G)$ in terms of the order and the chromatic number of $G$ are derived. The conditions are proved to be sufficient when $n\equiv 2 \pmod 3$ and $χ(G)=3$.
