摘要
色彩和问题询问，给定一个图 $G$ 和一个整数 $k$，是否存在一种着色 $c$，使得 $\forall v \text{ in } V, \sum_{v \in V}c(v) \leq k$。我们研究了在一些禁忌图定义的图类上，色彩和的复杂性。
主要发现
我们首先展示了三种已知框架能够完全分类在 $HH$-无小图和 $HH$-拓扑无小图的色彩和复杂性，适用于任何图集 $HH$，以及在任何有限图集 $HH$ 的 $HH$-子图无图上。为此，我们证明了色彩和在某些平面子立方图的特定细分上的新 NP-完全性结果。
接下来，我们考虑其他包含关系。我们正式化了一种新颖的框架，针对平面图和独立数有界的图的 NP-完全问题。对于该框架中的每个问题，我们在 $H$-诱导小图无图、$H$-诱导拓扑小图无图和 $H$-无图上获得了几乎完整的复杂性分类。我们证明色彩和属于此框架，其他几个问题也在其中。
此外，我们为诱导子图关系定义了一个更细致的框架。我们应用此框架以获得色彩和在 $H$-无图上的完整复杂性分类，以及其他几个问题。我们通过证明色彩和在最大团宽度为 $3$ 的图上是 NP-完全的，来证明该框架的选择是合理的。该结果补充了已知的关于最大团宽度为 $2$ 的图的多项式时间结果。
博主点评： 本文通过研究色彩和问题在不同图类中的复杂性，为图论中的禁忌图研究提供了新的视角。尤其是对 NP-完全性的深入分析，展现了图的结构特性如何影响计算复杂性，具有重要的理论意义和应用价值。希望未来能有更多这样的研究，进一步揭示图论中的复杂性秘密。