该研究旨在介绍一种基于矩阵的着色技术，将其应用于线性方程组和线性规划问题，并展示该技术可以显着降低解决线性规划的成本。

Jul, 2013

通过采用颜色精炼技术，结合线性规划，证明了图形同构的难题可在多项式时间内解决，该技术适用于大量的紧凑图，并且给了这一类图的识别复杂性的下界。

Feb, 2015

本文研究了用同构映射技术对图结构进行分析的方法，并通过引入颜色细化的广义，推广到了超图的结构分析。通过顶点彩色处理将超图和它的关联图中的同构映射联系起来，我们证明了当且仅当任何连通 Berig - 无圈超图 B 上的同构映射在两个超图 G 和 H 中的数量相同时，这种颜色细化的方法无法区分两个超图的结构。

Mar, 2019

研究随机 CSP 问题和多项式时间算法无法寻找解决方案的相位转变，并运用一般技术准确地证明 $k$- 着色的相位转变推出所有已知多项式时间算法的失败点。

Mar, 2008

对于五个及以下顶点的所有图 H，我们分类了（钻石，H）- 免费图的颜色问题的计算复杂性。我们的技术是将问题图归约到一个非常特殊的 k - 部分图上，其特定分解使得（钻石，P1+2P2）- 免费图具有有界的团宽。我们还能够证明其他四个新的（H1，H2）- 免费图案例的团宽有界。

Dec, 2015

本文研究计算机科学中基本的图着色问题的全面动态版本，在其中，图形正在进行边缘插入和删除，我们希望在每次插入和删除后以小的更新时间维护一个顶点着色。我们展示了如何使用对数更新时间维护 O（αlog n）着色，并提出了一种维护隐式动态着色的算法，该算法打破了最窄的低估，并对图的边缘维护一种算法划分，将其划分为 O（α）森林。

Feb, 2020

本文提出了关于图同构问题的方法，其中包括跟颜色精细算法和基于 Weisfeiler-Leman 算法的 k 维泛化相关的一些理论。我们证明了，如果对于所有树 T，T 到 G 的同态数量（Write out as Hom (T,G)）等于 T 到 H 的同态数量，那么颜色精细算法无法区分二者。而如果我们放弃非负性约束，在二者具有相同长度的路径时，寻找任意实数解的算法存在，且两个图形在分数同构时，颜色精细算法无法区分它们。最后，我们提出了一个几乎线性时间的算法来判定对于给定的图 G 和 H，是否存在一棵树 T 满足 Hom (T,G) = Hom (T,H)。

Feb, 2018

Ulman 的重构猜想与图的连通性有关，可以通过顶点删除子图的牌堆来确定，我们通过证明，当给定牌堆中的子图通过颜色细化同构测试等价时，仍然可以确定连通性，因此，这意味着通过重构图神经网络可以识别连通性，这是一种新近引入的受重构猜想启发的 GNN 架构。

Jun, 2024

通过定义图中的稳定和严格稳定着色，以理解网络反协调博弈中的非严格和严格纯策略均衡，从而表述出当此类着色存在和决策问题为 NP 难的情况，即找到纯策略均衡时的代价，并进一步考虑了定向情况的泛化版本，即反协调和协调兼备，证明了 NP 难度下的非严格均衡决策问题。此外，这些概念也与其他组合问题有多重联系，我们的结果解决了这些领域中的一些未解决的问题，特别是严格不友好划分问题的复杂性。

Aug, 2013

对于给定的图形应用 NP-hard Cluster Editing 问题的标准算法可能会产生偏向于数据子组（例如人口群体）的解决方案，我们提出了一种修改公平性约束条件，以确保每个子组的修改次数与其大小成比例，模型在现实社交网络上的经验分析表明，修改公平性的代价惊人地低。

Dec, 2021