In the mathematical discipline of graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, Shannon multigraphs, named after Claude Shannon by , are a special type of triangle graphs

Graph (mathematics)

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

, which are used in the field of edge coloring

Edge coloring

In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several...

 in particular.

A Shannon multigraph is multigraph

Multigraph

In mathematics, a multigraph or pseudograph is a graph which is permitted to have multiple edges, , that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge....

 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 , and edges respectively. This multigraph has maximum degree

Degree (graph theory)

In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted \deg. The maximum degree of a graph G, denoted by Δ, and the minimum degree of a graph, denoted by δ, are the maximum and minimum degree...

 . Its multiplicity (the maximum number of edges in a set of edges that all have the same endpoints) is .

Edge coloring

According to a theorem of , every multigraph with maximum degree has an edge coloring that uses at most colors. When is even, the example of the Shannon multigraph with multiplicity shows that this bound is tight: the vertex degree is exactly , but each of the edges is adjacent to every other edge, so it requires colors in any proper edge coloring.

A version of Vizing's theorem states that every multigraph with maximum degree and multiplicity may be colored using at most colors. Again, this bound is tight for the Shannon multigraphs.

External links

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