Shannon multigraph

• Shannon multigraphs
• 
  Sh(2)
• 
  Sh(3)
• 
  Sh(4)
• 
  Sh(5)
• 
  Sh(6)
• 
  Sh(7)

This nine-edge Shannon multigraph requires nine colors in any edge coloring; its vertex degree is six and its multiplicity is three.

According to a theorem of Shannon (1949), every multigraph with maximum degree ${\displaystyle \Delta }$ has an edge coloring that uses at most ${\displaystyle {\frac {3}{2}}\Delta }$ colors. When ${\displaystyle \Delta }$ is even, the example of the Shannon multigraph with multiplicity ${\displaystyle \Delta /2}$ shows that this bound is tight: the vertex degree is exactly ${\displaystyle \Delta }$, but each of the ${\displaystyle {\frac {3}{2}}\Delta }$ edges is adjacent to every other edge, so it requires ${\displaystyle {\frac {3}{2}}\Delta }$ colors in any proper edge coloring.

A version of Vizing's theorem (Vizing 1964) states that every multigraph with maximum degree ${\displaystyle \Delta }$ and multiplicity ${\displaystyle \mu }$ may be colored using at most ${\displaystyle \Delta +\mu }$ colors. Again, this bound is tight for the Shannon multigraphs.

• Fiorini, S.; Wilson, Robin James (1977), Edge-colourings of graphs, Research Notes in Mathematics, vol. 16, London: Pitman, p. 34, ISBN 0-273-01129-4, MR 0543798
• Shannon, Claude E. (1949), "A theorem on coloring the lines of a network", J. Math. Physics, 28: 148–151, doi:10.1002/sapm1949281148, hdl:10338.dmlcz/101098, MR 0030203.
• Volkmann, Lutz (1996), Fundamente der Graphentheorie (in German), Wien: Springer, p. 289, ISBN 3-211-82774-9.
• Vizing, V. G. (1964), "On an estimate of the chromatic class of a p-graph", Diskret. Analiz., 3: 25–30, MR 0180505.
• Vizing, V. G. (1965), "The chromatic class of a multigraph", Kibernetika, 1965 (3): 29–39, MR 0189915.

Wikimedia Commons has media related to Shannon multigraphs.

• Lutz Volkmann: Graphen an allen Ecken und Kanten. Lecture notes 2006, p. 242 (German)