图论 Injective 染色算法研讨纪要
2026年5月13日，路宇轩、英启锐、卢志钧就图论中的 Injective 染色问题进行了专题研讨。会议梳理了 Injective 染色的定义与现有成果，重点分析了基于 Star Forest 分解的算法思路，并对平方染色结合贪心策略的技术路线进行了可行性推演。
Injective 染色定义与现有成果
Injective 染色是强边染色的弱化版本，要求距离为 2 的边颜色不同，且在同一个三角形中邻边颜色也必须不同。从结构上看，Injective 染色等价于将图的边集分解为若干个诱导的 Star Forest——即同色边在原图中诱导出的子图是若干不相交的星图。
学术进展方面，Littlewood 猜想指出一般图的 Injective 色数渐进上界约为 (\frac{5}{4}\Delta^2)，目前最好的结果已推进至 (1.772\Delta^2)。在二部图上，色数渐进上界约为 (1.34\Delta^2)，已有明确结论。
算法思路与结构分析
为解决 Injective 染色问题，讨论提出了一种基于 Star Forest 分解的算法框架。
分解策略方面，核心思路是将图分解为若干个 Star Forest，每个 Star Forest 对应一种颜色，从而把边染色问题转化为寻找特定结构覆盖的问题。利用原图不含特定子图（如 (C_4)-free）的性质，可推导线图或平方图的局部稀疏性，进而应用局部稀疏图的染色技术。
平方染色转化方面，尝试通过给原图的平方图进行点染色，利用点染色的结果指导边染色，目标是用 (\Delta^2) 种颜色完成染色。在平方染色覆盖大部分边后，剩余未被染色的边数量可控制在 (\frac{1}{2}\Delta) 以内，此时通过贪心算法使用少量新颜色即可完成剩余边的染色。
可行性推演与瓶颈评估
会议对关键引理进行了验证，并识别了潜在的逻辑漏洞。
冲突边控制方面，通过分析可能导致冲突的"坏事件"，论证了在删除部分冲突边后，每个顶点关联的未染色边数量可被控制在约 (\frac{1}{2}\Delta) 以内。多轮迭代在理论上是可行的：若每轮能有效减少未染色边集，可逐步逼近最优解。
潜在反例方面，讨论指出在极端稠密图（如完全图）中，二阶邻域与一阶邻域的重合度极高，导致基于平方染色的隔离策略失效，无法有效降低色数。此外，对于任意图，寻找一个覆盖大部分边的 Star Forest 分解本身就非常困难，尤其在局部稀疏图中，该结构可能不存在或难以构造。
后续研究方向
技术路径调整。鉴于现有方法可能无法突破 1.7 的瓶颈，建议转向研究图的结构性质，寻找更精细的匹配结构（如 6s-matching），而非单纯依赖代数或概率方法。
AI 辅助研究。探讨了利用大模型辅助阅读文献和生成代码的可能性，但需注意其推理深度限制与算力消耗。
文献阅读。安排了具体的文献阅读任务，以进一步验证现有算法的边界，为后续的算法改进提供理论支撑。
