Misra & Gries边着色算法

Misra & Gries边着色算法是图论算法的一种，能够在多项式时间内找到任意图的一种边着色方案。这种着色算法最多使用种颜色，是该图节点的最大度数。这对于一些图而言是最优的，根据Vizing定理，最坏情况下，这种算法给出的结果比最优值多使用一种颜色。
该算法由Jayadev Misra和David Gries在1992年首次提出，是对Béla Bollobás提出的一种算法的简化。
对于边着色问题，该算法是已知最快的“几乎最优”算法。时间复杂度为。更小的时间复杂度在1985年Gabow等的一篇科技报告中提出，但从未被发表。
总体上来说，最优边着色问题是NP完全的，所以很可能并不存在多项式时间内的算法。同时也有指数级的算法给出了该问题的最优解。

路径的翻转

操作“翻转 cdX 路径”将该路径上的每个颜色为c 的边改变为d ，每个颜色为d 的边改变颜色为c 。如果X处于路径的末端，则翻转操作能够释放节点X上的一种颜色：如果 X 与 c 而非d 相邻，现在会变成与d 而非c 相邻，把颜色c 释放出来，可以给其他与X 邻接的边。这一翻转操作不会改变着色的有效性，因为对于路径末端的节点，只会有c 或 d 中的一种颜色，而对于边上的其他节点，翻转操作只是交换了边的颜色，并未增加新颜色。