Colorful Mathematics: Part II
This multigraph illustrates that a theorem of Claude Shannon (1916-2001), much better known for his work on information theory, gives the best possible upper bound. His theorem states that for a multigraph the chromatic index of a graph G is no more than 3Δ(G)/2 where Δ(G) denotes the maximal valence of any vertex in G.
You may be wondering if edge-colorings have any relation to the four-color problem. The remarkable answer is "yes." The connection comes because of the work of P. G. Tait (1831-1901) and Julius Petersen (1839-1910). Tait, in addition to his work on graph theory, was an early investigator of knots. Petersen, a Danish mathematician, did work on relating rule and compass constructions to the solution of algebraic equations.
Peter Tait and Julius Petersen
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Search Feature Column
Feature Column at a glance