论文标题
线图补充的颜色
Colorings of complements of line graphs
论文作者
论文摘要
我们的目的是证明列表的补充享有漂亮的着色属性。我们证明，对于此类中的所有图表，本地和通常的色度数相等。我们还证明了一个足够的条件，使色数等于天然上限。后一种条件的结果是对kneser Graph $ \ operatatorName {kg}（n，2）$的所有感应子图的完整表征，其色度等于其色数，即$ n-2 $。除上限外，Dol'nikov的定理还提供了下限，这是图理论中拓扑方法的经典结果。我们证明了$ \ operatorname {np} $ - 确定色数和任何这些范围之间的平等性的硬度。 拓扑方法特别适合研究超图形线图补充的着色特性。然而，本文中的所有证明都是基本的，我们还提供了有关拓扑方法涵盖我们一些结果的能力的简短讨论。
Our purpose is to show that complements of line graphs enjoy nice coloring properties. We show that for all graphs in this class the local and usual chromatic numbers are equal. We also prove a sufficient condition for the chromatic number to be equal to a natural upper bound. A consequence of this latter condition is a complete characterization of all induced subgraphs of the Kneser graph $\operatorname{KG}(n,2)$ that have a chromatic number equal to its chromatic number, namely $n-2$. In addition to the upper bound, a lower bound is provided by Dol'nikov's theorem, a classical result of the topological method in graph theory. We prove the $\operatorname{NP}$-hardness of deciding the equality between the chromatic number and any of these bounds. The topological method is especially suitable for the study of coloring properties of complements of line graphs of hypergraphs. Nevertheless, all proofs in this paper are elementary and we also provide a short discussion on the ability for the topological methods to cover some of our results.
