Shannon multigraph explained

In the mathematical discipline of graph theory, Shannon multigraphs, named after Claude Shannon by, are a special type of triangle graphs, which are used in the field of edge coloring in particular.

A Shannon multigraph is multigraph with 3 vertices for which either of the following conditions holds:

• a) all 3 vertices are connected by the same number of edges.

• b) as in a) and one additional edge is added.

More precisely one speaks of Shannon multigraph, if the three vertices are connected by

\left\lfloor (n)/(2) \right\rfloor , \left\lfloor (n)/(2) \right\rfloor and \left\lfloor (n +1)/(2) \right\rfloor edges respectively. This multigraph has maximum degree . Its multiplicity (the maximum number of edges in a set of edges that all have the same endpoints) is \left\lfloor (n +1)/(2) \right\rfloor .

Edge coloring

According to a theorem of, every multigraph with maximum degree

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

A version of Vizing's theorem states that every multigraph with maximum degree

\Delta and multiplicity \mu may be colored using at most \Delta + \mu colors. Again, this bound is tight for the Shannon multigraphs.

References

• • .
• .
• .
• .

External links

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