Bishop Edge Coloring
Bishop Edge Coloring
The graph of bishop moves on an chessboard has maximum degree , unless is even, in which case ; the graph can always have its edges colored in colors, where edges that meet get different colors. This Demonstration shows how the graph can be decomposed into paths, each of which can be 2-colored (or for some paths in the exceptional case, 1-colored), so that the total number of colors used is .
m×n
Δ=2m-2
m=n
Δ=2m-3
Δ
Δ
Graphs for which the edge chromatic number equals the maximum degree are said to be of class 1; this Demonstration describes a proof that bishops are class 1. The essence of the construction is given by restricting to the white bishop graph, where the lowest-left square is taken as white. Red dots mark the vertices of maximum degree; all colors must appear at such a vertex.