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

Feb, 2015

本文提出了关于图同构问题的方法，其中包括跟颜色精细算法和基于 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

介绍一类称为 Graph Motif Parameters 的图参数，介绍如何根据这个框架更快地计算固定大小的子图在大图中的个数，以及针对一类这样的参数进行问题的复杂度二分，其中包括用于颜色保留的子图计数。

May, 2017

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

Jun, 2024

通过引入颜色分离集的新概念，我们解决了通过持久化同调识别属性图的问题，并建立了区分图的必要和充分条件。基于这些理论洞察力，我们提出了一种称为 RePHINE 的方法，它有效地结合了顶点和边的持久化同调，证明了其在学习图的拓扑特征方面比标准持久化同调更强大，并在多个图分类基准测试中取得了优势。

Nov, 2023

本文从图同态的角度研究了图分类问题，提出了使用同态数作为嵌入映射的自然不变量，在近似不变函数的时候证明了同态向量的普适性，特别是在选择树宽有限的元素族时，同态方法比其他方法更有效率。

May, 2020

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

Jul, 2013

研究表明，当一个图参数满足两个线性代数条件：反射正性和指数秩连通性时，它可以被实现为到一个固定（加权）图的同态数量，这在统计物理学中可被视为顶点模型的划分函数的描述。

Apr, 2004

本文研究了新颖的随机图嵌入算法，能在预期的多项式时间内区分所有非同构图，并基于 Lovasz 的同态计数理论实现对任意图的函数逼近，结果在多个基准图学习任务上表现竞争力。

Jun, 2023

给定一个具有 n 个顶点和 m 条边的图，我们给出了一个算法来找到稳定着色的规范版本，具有最少的颜色，并且该算法的时间复杂度为 O ((m+n) log n)。该算法被广泛用于图同构测试算法的子程序中。

Sep, 2015