Wolfram Demonstrations Project

13,000+ Open Interactive Demonstrations
Powered by Notebook Technology »

Bishop Edge Coloring

Initializing live version
Download to Desktop

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

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 .

[more]

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.

[less]

Contributed by: Peter Saltzman (Berkeley, Calif.) and Stan Wagon (Macalester College) (January 2016)
Open content licensed under CC BY-NC-SA

Snapshots

Details

A graph admitting an edge coloring where the number of colors equals the maximum degree is said to be of "class 1". The result that bishops are class 1 appears in [1]. The coloring arises by considering various subgraphs that are each a union of disjoint paths.

The first subgraph consists of edges of length 1 having negative slope (the unit of length is the shortest distance between vertices) and edges of length having positive slope. That subgraph gets colored using 1 and 2; see Snapshot 1.

The next subgraph is the same, with the slopes reversed, and it uses colors 3 and 4. Then one uses edges of length 2 and for the next two subgraphs, and so on until the entire edge set is exhausted. Snapshot 2 shows the last case when .

Snapshot 3 shows the square even-height case, where the final subgraph uses edges of length with no slope restriction.

Reference

[1] P. Saltzman and S. Wagon, "Problem 3761," Crux Mathematicorum 38(7), 2012 p. 284; 39(7), 2013 pp. 325–327.

Permanent Citation

Peter Saltzman (Berkeley, Calif.) and Stan Wagon (Macalester College) "Bishop Edge Coloring"
http://demonstrations.wolfram.com/BishopEdgeColoring/
Wolfram Demonstrations Project
Published: January 11 2016

Embed Code

Take advantage of the Wolfram Notebook Emebedder for the recommended user experience.

Related Demonstrations More by Author
Browse all topics
Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send