Misra & Gries edge coloring algorithm
id:
misra-gries-edge-coloring-algorithm-294-16485950
title:
Misra & Gries edge coloring algorithm
text:
The Misra & Gries edge coloring algorithm is a polynomial time algorithm in graph theory that finds an edge coloring of any simple graph. The coloring produced uses at most Δ + 1 colors, where Δ is the maximum degree 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. It was first published by Jayadev Misra and David Gries in 1992. It is a simplification of a prior algor
brand slug:
wiki
category slug:
encyclopedia
description:
Algorithm in graph theory
original url:
https://en.wikipedia.org/wiki/Misra_%26_Gries_edge_coloring_algorithm
date created:
date modified:
2024-04-11T23:00:57Z
main entity:
{"identifier":"Q18808226","url":"https://www.wikidata.org/entity/Q18808226"}
image:
fields total:
13
integrity:
14