328:
312:
300:
288:
276:
264:
252:
235:
185:
142:
107:
515:
485:
387:
592:
435:
546:
455:
407:
357:
566:
765:
681:
613:
331:
This nine-edge
Shannon multigraph requires nine colors in any edge coloring; its vertex degree is six and its multiplicity is three.
197:
147:
112:
77:
33:
748:
490:
460:
362:
188:
194:. Its multiplicity (the maximum number of edges in a set of edges that all have the same endpoints) is
521:
571:
311:
299:
287:
275:
263:
251:
412:
677:
609:
531:
440:
392:
342:
650:
642:
732:
711:
664:
623:
728:
707:
691:
660:
619:
551:
327:
630:
25:
759:
37:
17:
655:
46:
646:
608:, Research Notes in Mathematics, vol. 16, London: Pitman, p. 34,
49:
with 3 vertices for which either of the following conditions holds:
326:
409:
is even, the example of the
Shannon multigraph with multiplicity
594:
colors. Again, this bound is tight for the
Shannon multigraphs.
719:
Vizing, V. G. (1965), "The chromatic class of a multigraph",
437:
shows that this bound is tight: the vertex degree is exactly
54:
a) all 3 vertices are connected by the same number of edges.
230:{\displaystyle \left\lfloor {\frac {n+1}{2}}\right\rfloor }
180:{\displaystyle \left\lfloor {\frac {n+1}{2}}\right\rfloor }
137:{\displaystyle \left\lfloor {\frac {n}{2}}\right\rfloor }
102:{\displaystyle \left\lfloor {\frac {n}{2}}\right\rfloor }
633:(1949), "A theorem on coloring the lines of a network",
487:
edges is adjacent to every other edge, so it requires
574:
554:
534:
493:
463:
443:
415:
395:
365:
345:
200:
150:
115:
80:
694:(1964), "On an estimate of the chromatic class of a
528:) states that every multigraph with maximum degree
586:
560:
540:
509:
479:
449:
429:
401:
381:
351:
229:
179:
136:
101:
187:edges respectively. This multigraph has maximum
66:More precisely one speaks of Shannon multigraph
59:b) as in a) and one additional edge is added.
8:
752:. Lecture notes 2006, p. 242 (German)
676:(in German), Wien: Springer, p. 289,
654:
604:Fiorini, S.; Wilson, Robin James (1977),
573:
553:
533:
494:
492:
464:
462:
442:
419:
414:
394:
366:
364:
344:
205:
199:
155:
149:
120:
114:
85:
79:
74:, if the three vertices are connected by
359:has an edge coloring that uses at most
339:, every multigraph with maximum degree
336:
244:
525:
29:
510:{\displaystyle {\frac {3}{2}}\Delta }
480:{\displaystyle {\frac {3}{2}}\Delta }
382:{\displaystyle {\frac {3}{2}}\Delta }
7:
517:colors in any proper edge coloring.
575:
535:
504:
474:
444:
416:
396:
376:
346:
16:In the mathematical discipline of
14:
749:Graphen an allen Ecken und Kanten
36:, which are used in the field of
32:, are a special type of triangle
310:
298:
286:
274:
262:
250:
1:
766:Parametric families of graphs
674:Fundamente der Graphentheorie
568:may be colored using at most
587:{\displaystyle \Delta +\mu }
782:
335:According to a theorem of
606:Edge-colourings of graphs
430:{\displaystyle \Delta /2}
45:A Shannon multigraph is
672:Volkmann, Lutz (1996),
541:{\displaystyle \Delta }
450:{\displaystyle \Delta }
402:{\displaystyle \Delta }
352:{\displaystyle \Delta }
647:10.1002/sapm1949281148
588:
562:
542:
511:
481:
451:
431:
403:
383:
353:
332:
231:
181:
138:
103:
589:
563:
543:
512:
482:
452:
432:
404:
384:
354:
330:
232:
182:
139:
104:
572:
561:{\displaystyle \mu }
552:
532:
491:
461:
441:
413:
393:
363:
343:
198:
148:
113:
78:
246:Shannon multigraphs
22:Shannon multigraphs
656:10338.dmlcz/101098
631:Shannon, Claude E.
584:
558:
538:
507:
477:
457:, but each of the
447:
427:
399:
379:
349:
333:
227:
177:
134:
99:
548:and multiplicity
502:
472:
374:
221:
171:
128:
93:
773:
735:
714:
700:Diskret. Analiz.
686:
667:
658:
635:J. Math. Physics
626:
593:
591:
590:
585:
567:
565:
564:
559:
547:
545:
544:
539:
522:Vizing's theorem
516:
514:
513:
508:
503:
495:
486:
484:
483:
478:
473:
465:
456:
454:
453:
448:
436:
434:
433:
428:
423:
408:
406:
405:
400:
388:
386:
385:
380:
375:
367:
358:
356:
355:
350:
314:
302:
290:
278:
266:
254:
236:
234:
233:
228:
226:
222:
217:
206:
193:
186:
184:
183:
178:
176:
172:
167:
156:
143:
141:
140:
135:
133:
129:
121:
108:
106:
105:
100:
98:
94:
86:
73:
781:
780:
776:
775:
774:
772:
771:
770:
756:
755:
746:Lutz Volkmann:
743:
718:
690:
684:
671:
629:
616:
603:
600:
570:
569:
550:
549:
530:
529:
489:
488:
459:
458:
439:
438:
411:
410:
391:
390:
361:
360:
341:
340:
325:
318:
315:
306:
303:
294:
291:
282:
279:
270:
267:
258:
255:
243:
207:
201:
196:
195:
191:
157:
151:
146:
145:
116:
111:
110:
81:
76:
75:
67:
40:in particular.
12:
11:
5:
779:
777:
769:
768:
758:
757:
754:
753:
742:
741:External links
739:
738:
737:
716:
688:
682:
669:
627:
614:
599:
596:
583:
580:
577:
557:
537:
506:
501:
498:
476:
471:
468:
446:
426:
422:
418:
398:
378:
373:
370:
348:
337:Shannon (1949)
324:
321:
320:
319:
316:
309:
307:
304:
297:
295:
292:
285:
283:
280:
273:
271:
268:
261:
259:
256:
249:
247:
242:
239:
225:
220:
216:
213:
210:
204:
175:
170:
166:
163:
160:
154:
132:
127:
124:
119:
97:
92:
89:
84:
64:
63:
62:
61:
56:
26:Claude Shannon
24:, named after
13:
10:
9:
6:
4:
3:
2:
778:
767:
764:
763:
761:
751:
750:
745:
744:
740:
734:
730:
726:
722:
717:
713:
709:
705:
701:
697:
693:
692:Vizing, V. G.
689:
685:
683:3-211-82774-9
679:
675:
670:
666:
662:
657:
652:
648:
644:
640:
636:
632:
628:
625:
621:
617:
615:0-273-01129-4
611:
607:
602:
601:
597:
595:
581:
578:
555:
527:
523:
520:A version of
518:
499:
496:
469:
466:
424:
420:
389:colors. When
371:
368:
338:
329:
323:Edge coloring
322:
313:
308:
301:
296:
289:
284:
277:
272:
265:
260:
253:
248:
245:
240:
238:
223:
218:
214:
211:
208:
202:
190:
173:
168:
164:
161:
158:
152:
130:
125:
122:
117:
95:
90:
87:
82:
71:
60:
57:
55:
52:
51:
50:
48:
43:
42:
41:
39:
38:edge coloring
35:
31:
30:Vizing (1965)
27:
23:
19:
747:
727:(3): 29–39,
724:
720:
703:
699:
695:
673:
638:
634:
605:
519:
334:
69:
65:
58:
53:
44:
21:
18:graph theory
15:
721:Kibernetika
641:: 148–151,
526:Vizing 1964
598:References
47:multigraph
706:: 25–30,
698:-graph",
582:μ
576:Δ
556:μ
536:Δ
505:Δ
475:Δ
445:Δ
417:Δ
397:Δ
377:Δ
347:Δ
760:Category
241:Examples
224:⌋
203:⌊
174:⌋
153:⌊
131:⌋
118:⌊
96:⌋
83:⌊
733:0189915
712:0180505
665:0030203
624:0543798
731:
710:
680:
663:
622:
612:
189:degree
34:graphs
317:Sh(7)
305:Sh(6)
293:Sh(5)
281:Sh(4)
269:Sh(3)
257:Sh(2)
725:1965
678:ISBN
610:ISBN
144:and
651:hdl
643:doi
68:Sh(
28:by
762::
729:MR
723:,
708:MR
702:,
661:MR
659:,
649:,
639:28
637:,
620:MR
618:,
237:.
109:,
20:,
736:.
715:.
704:3
696:p
687:.
668:.
653::
645::
579:+
524:(
500:2
497:3
470:2
467:3
425:2
421:/
372:2
369:3
219:2
215:1
212:+
209:n
192:n
169:2
165:1
162:+
159:n
126:2
123:n
91:2
88:n
72:)
70:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
