Shannon multigraph

<h2 id="examples">Examples</h2>

<h2 id="edge-coloring">Edge coloring</h2>

<p>According to a theorem of Shannon (1949), every multigraph with maximum degree 
  
    
      
        Δ
      
    
    {\displaystyle \Delta }
  
 has an edge coloring that uses at most 
  
    
      
        
          
            3
            2
          
        
        Δ
      
    
    {\displaystyle {\frac {3}{2}}\Delta }
  
 colors. When 
  
    
      
        Δ
      
    
    {\displaystyle \Delta }
  
 is even, the example of the Shannon multigraph with multiplicity 
  
    
      
        Δ
        
          /
        
        2
      
    
    {\displaystyle \Delta /2}
  
 shows that this bound is tight: the vertex degree is exactly 
  
    
      
        Δ
      
    
    {\displaystyle \Delta }
  
, but each of the 
  
    
      
        
          
            3
            2
          
        
        Δ
      
    
    {\displaystyle {\frac {3}{2}}\Delta }
  
 edges is adjacent to every other edge, so it requires 
  
    
      
        
          
            3
            2
          
        
        Δ
      
    
    {\displaystyle {\frac {3}{2}}\Delta }
  
 colors in any proper edge coloring.
</p><p>A version of <a href="/facts/Vizing%27s_theorem/hHtEtK9t">Vizing's theorem</a> (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.
</p>

<ul><li>Fiorini, S.; Wilson, Robin James (1977), <i>Edge-colourings of graphs</i>, Research Notes in Mathematics, vol. 16, London: Pitman, p. 34, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-273-01129-4, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0543798">0543798</a></li>
<li><a href="/facts/Claude_Shannon/EremsCws">Shannon, Claude E.</a> (1949), "A theorem on coloring the lines of a network", <i>J. Math. Physics</i>, 28: 148–151, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1002%2Fsapm1949281148">10.1002/sapm1949281148</a>, <a href="/facts/Hdl_(identifier)/rdebSxmC">hdl</a>:<a href="https://hdl.handle.net/10338.dmlcz%2F101098">10338.dmlcz/101098</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0030203">0030203</a>.</li>
<li>Volkmann, Lutz (1996), <i>Fundamente der Graphentheorie</i> (in German), Wien: Springer, p. 289, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 3-211-82774-9.</li>
<li><a href="/facts/Vadim_G._Vizing/oHwYWIsH">Vizing, V. G.</a> (1964), "On an estimate of the chromatic class of a <i>p</i>-graph", <i>Diskret. Analiz.</i>, 3: 25–30, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0180505">0180505</a>.</li>
<li>Vizing, V. G. (1965), "The chromatic class of a multigraph", <i>Kibernetika</i>, 1965 (3): 29–39, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0189915">0189915</a>.</li></ul>
<h2 id="external-links">External links</h2>

Wikimedia Commons has media related to Shannon multigraphs.

<ul><li>Lutz Volkmann: <i><a href="http://www.math2.rwth-aachen.de/files/gt/buch/graphen_an_allen_ecken_und_kanten.pdf">Graphen an allen Ecken und Kanten</a></i>. Lecture notes 2006, p. 242 (German)</li></ul>

Shannon multigraph open-in-new

Shannon multigraph