即使是在连通的正则图上，兼容性问题也属于NP完全问题（NP-complete）

《Discrete Applied Mathematics》：Conformability is NP-complete, even on connected regular graphs

　　摘要
如果一个图G存在一种适当的(Δ(G)+1)着色，且在包括空色类在内的Δ(G)+1个颜色类中，最多只有∑v∈V(G)(Δ(G)?dG(v))的奇偶性与|V(G)|的奇偶性不同，那么图G是符合规则的。最近的研究中尚未确定判断图是否符合规则的复杂度，但对于某些图类的积极结果表明该问题可能是多项式时间可解的。我们通过证明符合规则性是NP完全问题来解决这个一般性问题。即使对于独立数为α(G)=3且最大度Δ(G)≥|V(G)|/2的连通正则图，这一难度也依然存在。特别地，当每个颜色类的奇偶性都被强制为该颜色的度数时，NP完全性仍然成立。归约过程从三元素完全三角填充开始，在保持相关三角填充的同时对源图进行规范处理，然后取其补图。在补图中，符合规则的颜色类对应于规范化图中的奇数团；无K4图的条件将这些团限制为单元素或三角形，而可用颜色的数量恰好决定了所需的不相交三角形数量。

引言
本文讨论的所有图都是有限的、简单的和无向图。对于图G，设Δ(G)为其最大度，并定义其亏量为def(G)=∑v∈V(G)(Δ(G)?dG(v))。
一个适当的顶点着色φ:V(G)→{1,…,Δ(G)+1}是符合规则的，如果最多只有def(G)个颜色类（包括空类）的奇偶性与|V(G)|的奇偶性不同。相应的决策问题是：
问题1 实例：一个连通图G。
问题：G是否符合规则？
这里的连通输入约定遵循了最近对该问题的表述[1]。这一约定很重要：符合规则性取决于全局参数Δ(G)和|V(G)|，因此问题不能分解为连通分量。我们的归约过程产生了连通实例。
Chetwynd和Hilton在研究总着色猜想时引入了符合规则的概念[2]。图G的总着色是为顶点和边分配颜色，使得相邻或 incident 的元素接收不同的颜色。总色数χ′′(G)=Δ(G)+1的图被称为类型1图。Chetwynd和Hilton观察到每个类型1图都是符合规则的。因此，符合规则性是类型1总着色的一个结构性必要条件，但它纯粹是作为一个顶点着色属性定义的。尽管确定总色数通常是NP难的[3]，但这并不影响由符合规则性所捕捉的顶点着色障碍的复杂性。
符合规则性在总着色理论中也具有更广泛的作用。它出现在符合规则性猜想以及关于完全临界图和过满猜想的相关工作中[4],[5]。在高阶正则图中，符合规则性条件与类型1总着色相互作用：Chetwynd、Hilton和Zhao获得了高最小度总着色结果，并为某些奇数阶正则图提出了必要充分条件[6],[7]。因此，我们归约过程中涉及的密集正则图是一个符合规则性与总着色最接近的领域。
在本文之前，已有的证据大多是积极的。Chetwynd和Hilton对循环图和完全图进行了分类[2]；Hilton和Hind证明了每个非符合规则的图G（其中Δ(G)≥2）都满足def(G)≤Δ(G)?2，当|V(G)|为偶数且Δ(G)为奇数时，更严格的界限是def(G)≤Δ(G)?3[8,引理9]；Zorzi、de Figueiredo、Machado、Zatesko和Souza对循环图的幂进行了符合规则性的分类[9]；并且也从符合规则性的角度研究了正则线图[10]。
算法证据也指向了该问题的可解性。Hajnal和Szemerédi的定理保证了公平着色是可行的[11]，并且可以在多项式时间内构造[12]，这已被用来构造大型符合规则的图族[1]。最近关于循环图的工作明确将符合规则性表述为一个决策问题，指出其复杂性未知，并通过公平着色构造和无限正类提供了可解性的线索[1]，最终猜想符合规则性是多项式时间可解的[1]。随后的一篇论文为正则二分图和次立方图证明了多项式时间算法，同时再次将一般问题留待解决[13]。这种与总着色的分离是有意义的：即使对于每个固定的k≥3的k-正则二分图，总着色也是NP难的[14]，而在正则二分图中，普通符合规则性是多项式时间可解的[13]。
我们将这个问题与最近的一个强化版本区分开来。Faria、Nigro和Sasaki引入了强符合规则着色，这些着色满足额外的条件，旨在表征是否可以扩展到(Δ+1)总着色[15]。该强化问题的难度并不决定符合规则性本身：普通符合规则性不要求顶点着色是否可以扩展到总着色。
我们的结果解决了原有的决策问题。
定理2
决策问题“符合规则性”是NP完全的。此外，当限制在满足α(G)=3且Δ(G)≥|V(G)|/2的奇数阶连通正则图时，它仍然是NP完全的。
我们的贡献有四个方面：
• 我们证明了符合规则性是NP完全的，从而解决了决策问题。
• 我们展示了即使在亏量为零的奇数阶正则图中，难度也仍然存在。
• 我们获得了独立数恰好为三的密集连通正则难题实例。
• 我们为无K4图引入了一个保持三角形的规范化引理。
定理2中的限制是强的。如果G是正则图，则def(G)=0。因此，当|V(G)|为奇数时，一个符合规则的着色恰好是一个适当的(Δ(G)+1)着色，其中Δ(G)+1个颜色类中的每一个都是奇数。空色类自动被排除在外。因此，难度在亏量为零时就已经出现。
这也加强了与已知积极结果的对比。已知的多项式时间情况包括稀疏图（如次立方图）以及二分正则图。我们的难题实例在两个方面与之相反。首先，它们是密集的。在归约过程中，我们在N个顶点上构造了一个度为r的正规辅助图H，并安排N?1?r≥N/2。输出图G=Hˉ，所以G是度为N?1?r的正则图，因此其度至少是其阶数的一半。其次，难题实例的独立数是有界的，即α(G)=3；相比之下，每个阶数为N的二分图都有一个大小至少为N/2的独立集。因此，仅凭正则性并不能决定哪些情况是多项式时间可解的，哪些是NP完全的；密度和小独立数也很重要。
归约的核心很简单。从无K4图中的一个完美三角填充实例开始，我们构造了一个没有创建任何新三角形的正规无K4图H，然后设置G=Hˉ。G的颜色类是G的独立集，等价于H的团。由于H是无K4图，G的每个奇数非空颜色类的大小要么是1，要么是3。然后一个计数恒等式恰好决定了所需的大小为3的类数量，而这些类正是H中的不相交三角形。

本文的组织结构如下。第2节确定符号并陈述了完美三角填充问题。第3节进行一个小填充步骤，使所需的三角形数量与后续的度参数对齐。第4节证明了保持三角形的规范化引理。第5节完成了补图归约并证明了定理2。第6节讨论了结果和开放方向。

背景和符号
我们用ω(G)表示图G的团数，用α(G)表示其独立数。G的补图表示为Gˉ。除非另有说明，一个颜色类可能是空的；在测试符合规则性时包括空颜色类。
以下基本观察是符合规则性和三角填充之间的桥梁。
命题3
设G是一个奇数阶N的正则图。那么G是符合规则的当且仅当G存在一种适当的(Δ(G)+1)着色，其中所有Δ(G)+1个颜色类都是非空的且奇数。
证明

由于G
填充源实例
设X0是问题4的一个实例，所以|V(X0)|=3p0。填充步骤增加目标度数p，直到偶数度参数d?2p主导填充图的最大度，同时保持yes/no答案。之后，恒等式p=d/2正是补图计数论证所强制的。
选择一个整数q≥1，使得2(p0+q)≥Δ(X0)。例如，q=max{1,?Δ(X0)/2??p0}就足够了，这是一个多项式时间选择。定义X?X0∪?q，K3,p?p0+q，d?2p。那么|V(X)|=3p，d是偶数，且X是正则的。

规范化而不创建三角形
技术目标是用一个保持三角形的正规无K4图H替换填充后的无K4图X。这三个要求对于補图步骤都是必要的：正则性使亏量为零，奇数阶使符合规则的颜色类为奇数，无K4性确保H中的奇数团的大小只有1或3。中间图H不需要是连通的；只有最终的实例G=Hˉ必须是连通的，这将从其最小度得出。

我们现在完成归约。从X0开始，按照引理6形成X。应用引理8得到一个度为N≥2d+2的d-正则无K4图H。最后，定义G?Hˉ。
因为H在N个顶点上是d-正則的，所以G是度为Δ(G)=N?1?d的正则图。因此Δ(G)+1=N?d。由于G是正则的，def(G)=0。由于N是奇数，命题3表明G的符合规则性等价于存在一个恰好有N?d个非空奇数颜色类的适当着色。
此外，q≥1确保X包含一个三角形，

结论
我们证明了符合规则性是NP完全的，解决了符合规则性的一般复杂性问题。即使在独立数恰好为三且度至少为其阶数一半的连通正则图中，难度也存在。在这种情况下，亏量为零，所以每个颜色类的奇偶性必须恰好与其阶数相同；因此，难度来自于(Δ+1)着色的奇偶性结构，而不是由正亏量允许的特殊类。

在准备手稿过程中声明生成式AI和AI辅助技术
在准备这项工作时，作者使用了OpenAI的ChatGPT和Anthropic的Claude来支持头脑风暴、组织、LaTeX起草和编辑修订。使用这些工具后，作者根据需要审查和编辑了内容，并对发表文章的内容负全部责任。

资助
József Pintér由项目编号KDP-IKT-2023-900-I1-00000957/000003资助，该资助由匈牙利文化与创新部通过国家研究、发展和创新基金提供，该基金是在KDP-2023资助计划下支持的。资助者没有参与研究的设计、手稿的编写或决定提交文章发表。

利益冲突声明
作者声明他们没有已知的可能影响本文工作的竞争性财务利益或个人关系。

致谢
作者感谢Luérbio Faria、Mauro Nigro、Myriam Preissmann和Diana Sasaki，他们在符合规则性方面的工作将复杂性问题提到了前台，并为本文提供了起点。