在冲突约束下的公平分配问题中，目标是以公平的方式将图的顶点分配给代理，使得没有两个相邻的顶点被分配给同一个代理。我们通过三种公平标准来研究这一问题：针对偏好顺序的随机优势嫉妒无关性（SD-EF1）、针对单调加法估值的嫉妒无关性（EF1），以及针对一般加法估值的嫉妒无关性（EF[1,1]）。为此，我们引入了强着色数的变体层次，这一图论量在九十年代初由 Alon 和 Fellows 独立提出。我们的结果揭示了冲突约束下的公平分配与这一层次的前两级之间的密切联系，为存在性和算法结果提供了统一的途径。
对于 SD-EF1，我们完全表征了保证公平分配所需的代理数量，适用于每一种共同偏好顺序。对于 EF1 和 EF[1,1]，我们提供了类似的充分条件，扩展了 Equbal 等人关于路径图的结果。我们还展示了，与 SD-EF1 设置不同，EF1 和 EF[1,1] 的充分条件在一般情况下并非必要。我们的框架在最大度数方面产生了存在性和算法上的后果。我们获得了每个最大度数为 $\Delta$ 的图在代理数量至少为 $3\Delta-1$ 时，能够实现 SD-EF1、EF1 和 EF[1,1] 的分配。进一步地，对于任意的 $\varepsilon > 0$，我们提供了确定性多项式时间算法，当代理数量至少为 $(3+\varepsilon)\Delta$ 时，可以找到这样的分配。这些保证增强了 Barman 和 Viswanathan 在公平着色方面的早期工作。
博主点评： 本文通过引入强着色数的概念，深入探讨了图论在公平分配中的应用，提供了实用的算法与理论支持。这为解决复杂的资源分配问题提供了新的思路，尤其是在处理冲突约束的情况下，具有重要的学术价值和实际意义。