---
tag: 7VHNFBZRF1
kind: concept
name: Misra & Gries edge-coloring algorithm
sources:
  - wikipedia: en:44498198@r1296446907
    locator: Misra & Gries edge-coloring algorithm
    note: adopted
    mention: wikipedia://en/44498198
    sections: [Summary]
same_as:
  wikidata: Q18808226
  wikipedia: Misra & Gries edge-coloring algorithm
inventory: [51TEPKSBA0]
---

## Summary

The **Misra & Gries edge-coloring algorithm** is a polynomial-time algorithm in graph theory that finds an [[edge coloring|0B5WCC02AN]] of any simple graph. The coloring produced uses at most $\Delta+1$ colors, where $\Delta$ is the maximum [[degree|0KS0KRDV4Y]] of the graph. This is optimal for some graphs, and it uses at most one color more than optimal for all others. The existence of such a coloring is guaranteed by Vizing's theorem.