698:
682:
670:
26:
656:
538:
725:
Brinkmann, G. "Generating Cubic Graphs Faster Than
Isomorphism Checking." Preprint 92-047 SFB 343. Bielefeld, Germany: University of Bielefeld, 1992.
737:
Brinkmann, G. and
Meringer, M. "The Smallest 4-Regular 4-Chromatic Graphs with Girth 5." Graph Theory Notes of New York 32, 40-41, 1997.
697:
542:
846:
397:
681:
189:
with 21 vertices and 42 edges discovered by Gunnar
Brinkmann in 1992. It was first published by Brinkmann and Meringer in 1997.
430:
165:
669:
892:
830:
299:. However, despite this disproof, it remains of interest to find examples and only very few are known.
424:
201:
897:
409:
74:
64:
205:
44:
303:
84:
8:
292:
220:
54:
812:
94:
792:
865:
158:
868:
842:
804:
772:
688:
193:
111:
248:
704:
197:
131:
121:
227:-regular graph (except for odd cycles and cliques) has chromatic number at most
208:. It is the smallest 4-regular graph of girth 5 with chromatic number 4. It has
413:
296:
209:
154:
100:
886:
295:
is O(Δ/log Δ) where Δ is the maximum vertex degree and the O introduces
186:
760:
777:
287: = 5. GrĂĽnbaum's conjecture was disproved for sufficiently large
213:
178:
141:
279: = 4 of this conjecture and the Brinkmann graph solves the case
247:. In connection with these two results and several examples including the
174:
847:
10.1002/(SICI)1097-0118(199804)27:4<177::AID-JGT1>3.0.CO;2-K
816:
873:
25:
808:
417:
651:{\displaystyle (x^{6}+3x^{5}-8x^{4}-21x^{3}+27x^{2}+38x-41)^{2}}
392:
863:
291:
by
Johannsen, who showed that the chromatic number of a
803:(10), Mathematical Association of America: 1088–1092,
545:
533:{\displaystyle (x-4)(x-2)(x+2)(x^{3}-x^{2}-2x+1)^{2}}
433:
412:
and its full automorphism group is isomorphic to the
251:, Branko GrĂĽnbaum conjectured in 1970 that for every
200:
5, radius 3, diameter 3 and girth 5. It is also a 3-
650:
532:
884:
231:. It was also known since 1959 that, for every
750:. Master Thesis, University of TĂĽbingen, 2018
420:, including both rotations and reflections.
416:of order 14, the group of symmetries of a
24:
776:
791:
763:(1959), "Graph theory and probability",
795:(1970), "A problem in graph coloring",
675:Alternative drawing of Brinkmann Graph.
403:
885:
733:
731:
864:
759:
829:
271:. The Chvátal graph solves the case
748:Engineering Linear Layouts with SAT
728:
13:
14:
909:
857:
696:
680:
668:
765:Canadian Journal of Mathematics
823:
785:
753:
740:
719:
639:
546:
521:
479:
476:
464:
461:
449:
446:
434:
166:Table of graphs and parameters
1:
797:American Mathematical Monthly
712:
707:of the Brinkmann graph is 5.
408:The Brinkmann graph is not a
243:-chromatic graphs with girth
691:of the Brinkmann graph is 4.
7:
267:-regular graphs with girth
10:
914:
661:
427:of the Brinkmann graph is
306:of the Brinkmann graph is
425:characteristic polynomial
164:
150:
140:
130:
120:
110:
93:
83:
73:
63:
53:
43:
35:
23:
18:
835:Journal of Graph Theory
833:(1998), "ω, Δ, and χ",
410:vertex-transitive graph
778:10.4153/CJM-1959-003-9
652:
534:
202:vertex-connected graph
653:
535:
543:
431:
404:Algebraic properties
304:chromatic polynomial
206:edge-connected graph
293:triangle-free graph
30:The Brinkmann graph
866:Weisstein, Eric W.
648:
530:
893:Individual graphs
869:"Brinkmann graph"
283: = 4,
171:
170:
905:
879:
878:
851:
849:
827:
821:
819:
789:
783:
781:
780:
757:
751:
744:
738:
735:
726:
723:
700:
689:chromatic number
684:
672:
657:
655:
654:
649:
647:
646:
622:
621:
606:
605:
590:
589:
574:
573:
558:
557:
539:
537:
536:
531:
529:
528:
504:
503:
491:
490:
395:
194:chromatic number
112:Chromatic number
39:Gunnar Brinkmann
28:
16:
15:
913:
912:
908:
907:
906:
904:
903:
902:
883:
882:
860:
855:
854:
828:
824:
809:10.2307/2316101
790:
786:
758:
754:
745:
741:
736:
729:
724:
720:
715:
708:
705:chromatic index
701:
692:
685:
676:
673:
664:
642:
638:
617:
613:
601:
597:
585:
581:
569:
565:
553:
549:
544:
541:
540:
524:
520:
499:
495:
486:
482:
432:
429:
428:
406:
391:
221:Brooks’ theorem
198:chromatic index
183:Brinkmann graph
157:
122:Chromatic index
104:
31:
19:Brinkmann graph
12:
11:
5:
911:
901:
900:
898:Regular graphs
895:
881:
880:
859:
858:External links
856:
853:
852:
841:(4): 177–212,
822:
784:
752:
746:Jessica Wolz,
739:
727:
717:
716:
714:
711:
710:
709:
702:
695:
693:
686:
679:
677:
674:
667:
663:
660:
645:
641:
637:
634:
631:
628:
625:
620:
616:
612:
609:
604:
600:
596:
593:
588:
584:
580:
577:
572:
568:
564:
561:
556:
552:
548:
527:
523:
519:
516:
513:
510:
507:
502:
498:
494:
489:
485:
481:
478:
475:
472:
469:
466:
463:
460:
457:
454:
451:
448:
445:
442:
439:
436:
414:dihedral group
405:
402:
297:big O notation
210:book thickness
169:
168:
162:
161:
152:
148:
147:
144:
138:
137:
134:
132:Book thickness
128:
127:
124:
118:
117:
114:
108:
107:
102:
97:
91:
90:
87:
81:
80:
77:
71:
70:
67:
61:
60:
57:
51:
50:
47:
41:
40:
37:
33:
32:
29:
21:
20:
9:
6:
4:
3:
2:
910:
899:
896:
894:
891:
890:
888:
876:
875:
870:
867:
862:
861:
848:
844:
840:
836:
832:
826:
818:
814:
810:
806:
802:
798:
794:
788:
779:
774:
770:
766:
762:
756:
749:
743:
734:
732:
722:
718:
706:
699:
694:
690:
683:
678:
671:
666:
665:
659:
643:
635:
632:
629:
626:
623:
618:
614:
610:
607:
602:
598:
594:
591:
586:
582:
578:
575:
570:
566:
562:
559:
554:
550:
525:
517:
514:
511:
508:
505:
500:
496:
492:
487:
483:
473:
470:
467:
458:
455:
452:
443:
440:
437:
426:
421:
419:
415:
411:
401:
399:
394:
389:
385:
381:
378:+ 18168142566
377:
374:- 30480167403
373:
370:+ 36783818141
369:
366:- 34133692383
365:
362:+ 25384350310
361:
358:- 15547364853
357:
353:
349:
345:
341:
337:
333:
329:
325:
321:
317:
313:
309:
305:
300:
298:
294:
290:
286:
282:
278:
275: =
274:
270:
266:
262:
258:
254:
250:
249:Chvátal graph
246:
242:
238:
234:
230:
226:
222:
217:
215:
211:
207:
203:
199:
195:
190:
188:
187:regular graph
184:
180:
176:
167:
163:
160:
156:
153:
149:
145:
143:
139:
135:
133:
129:
125:
123:
119:
115:
113:
109:
105:
98:
96:
95:Automorphisms
92:
88:
86:
82:
78:
76:
72:
68:
66:
62:
58:
56:
52:
48:
46:
42:
38:
34:
27:
22:
17:
872:
838:
834:
825:
800:
796:
793:GrĂĽnbaum, B.
787:
768:
764:
755:
747:
742:
721:
422:
407:
387:
386:+ 1242405972
383:
382:- 6896700738
379:
375:
371:
367:
363:
359:
355:
354:+ 7987607279
351:
350:- 3483798283
347:
346:+ 1299042255
343:
339:
335:
331:
327:
323:
319:
315:
311:
307:
301:
288:
284:
280:
276:
272:
268:
264:
260:
259:there exist
256:
252:
244:
240:
239:there exist
236:
232:
228:
224:
218:
214:queue number
191:
182:
179:graph theory
175:mathematical
172:
142:Queue number
831:Reed, B. A.
761:Erdős, Paul
342:- 415278052
338:+ 113675219
263:-chromatic
159:Hamiltonian
36:Named after
887:Categories
713:References
390:(sequence
334:- 26500254
151:Properties
874:MathWorld
771:: 34–38,
633:−
592:−
576:−
506:−
493:−
456:−
441:−
330:+ 5207711
177:field of
418:heptagon
326:- 848708
322:+ 111881
223:, every
204:and a 3-
155:Eulerian
75:Diameter
45:Vertices
817:2316101
662:Gallery
396:in the
393:A159192
318:- 11480
192:It has
185:is a 4-
173:In the
815:
212:3 and
181:, the
65:Radius
813:JSTOR
314:+ 861
85:Girth
55:Edges
703:The
687:The
423:The
398:OEIS
310:- 42
302:The
255:and
235:and
99:14 (
843:doi
805:doi
773:doi
400:).
219:By
216:2.
196:4,
889::
871:.
839:27
837:,
811:,
801:77
799:,
769:11
767:,
730:^
658:.
636:41
627:38
611:27
595:21
59:42
49:21
877:.
850:.
845::
820:.
807::
782:.
775::
644:2
640:)
630:x
624:+
619:2
615:x
608:+
603:3
599:x
587:4
583:x
579:8
571:5
567:x
563:3
560:+
555:6
551:x
547:(
526:2
522:)
518:1
515:+
512:x
509:2
501:2
497:x
488:3
484:x
480:(
477:)
474:2
471:+
468:x
465:(
462:)
459:2
453:x
450:(
447:)
444:4
438:x
435:(
388:x
384:x
380:x
376:x
372:x
368:x
364:x
360:x
356:x
352:x
348:x
344:x
340:x
336:x
332:x
328:x
324:x
320:x
316:x
312:x
308:x
289:k
285:l
281:k
277:l
273:k
269:l
265:k
261:k
257:l
253:k
245:l
241:k
237:l
233:k
229:k
225:k
146:2
136:3
126:5
116:4
106:)
103:7
101:D
89:5
79:3
69:3
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
