page_title: Misra & Gries edge coloring algorithm
section_title: Fans
hierarchical_section_title: Misra & Gries edge coloring algorithm / Fans
caption_attribution_description: English: Illustrates various bicolored paths in the Misra and Gries edge coloring algorithm
context_page_description: The Misra & Gries edge coloring algorithm is a polynomial time algorithm in graph theory that finds an edge coloring of any graph. The coloring produces uses at most colors, where is the maximum degree of the graph. This is optimal for some graphs, and by Vizing's theorem it uses at most one color more than the optimal for all others.
  It was first published by Jayadev Misra and David Gries in 1992. It is a simplification of a prior algorithm by Béla Bollobás.
  This algorithm is the fastest known almost-optimal algorithm for edge coloring, executing in time. A faster time bound of was claimed in a 1985 technical report by Gabow et al., but this has never been published.
  In general, optimal edge coloring is NP-complete, so it is very unlikely that a polynomial time algorithm exists. There are however exponential time exact edge coloring algorithms that give an optimal solution.
context_section_description: A color x is said to be free of an edge (u,v) on u if c(u,z) ≠ x for all (u,z)  E(G) : z≠v.
  A fan of a vertex u is a sequence of vertices F[1:k] that satisfies the following conditions:
  F[1:k] is a non-empty sequence of distinct neighbors of u
  (F[1],u)  E(G) is uncolored
  The color of (F[i+1],u) is free on F[i] for 1 ≤ i < k
  Given a fan F, any edge (F[i], X) for 1 ≤ i ≤ k is a fan edge. Let c and d be colors. A cdX-path is an edge path that goes through vertex X, only contains edges colored c and d and is maximal (we cannot add any other edge as it would include edges with a color not in {c, d}). Note that only one such path exists for a vertex X, as at most one edge of each color can be adjacent to a given vertex.
caption: Examples of cdx paths: ac,cg,gd is a red-green_c path and bd,dg is a red-oranged path.
exif: {}