531:. That is, the edges of the graph may be assigned a direction, and a number from the set {1, 2, 3}, such that the sum of the incoming numbers minus the sum of the outgoing numbers at each vertex is divisible by four. As Tutte showed, for cubic graphs such an assignment exists if and only if the edges can be colored by three colors, so the conjecture would follow from the snark conjecture in this case. However, proving the snark conjecture would not settle the question of the existence of 4-flows for non-cubic graphs.
370:(an edge connecting a vertex to itself) cannot be colored without causing the same color to appear twice at that vertex, a violation of the usual requirements for graph edge coloring. Additionally, a cycle consisting of two vertices connected by two edges can always be replaced by a single edge connecting their two other neighbors, simplifying the graph without changing its three-edge-colorability. For these reasons, snarks are generally restricted to
351:, the number of colors needed for the edges of a cubic graph is either three ("class one" graphs) or four ("class two" graphs), so snarks are cubic graphs of class two. However, in order to avoid cases where a snark is of class two for trivial reasons, or is constructed in a trivial way from smaller graphs, additional restrictions on connectivity and cycle lengths are often imposed. In particular:
29:
41:
363:, the subgraphs on either side of the bridge have an odd number of vertices each. Whichever of three colors is chosen for the bridge, their odd number of vertices prevents these subgraphs from being covered by cycles that alternate between the other two colors, as would be necessary in a 3-edge-coloring. For this reason, snarks are generally required to be bridgeless.
397:
requires snarks to be cyclically 4-edge-connected. That means there can be no subset of three or fewer edges, the removal of which would disconnect the graph into two subgraphs each of which has at least one cycle. Brinkmann et al. define a snark to be a cubic and cyclically 4-edge-connected graph of
377:
If a graph contains a triangle, then it can again be simplified without changing its three-edge-colorability, by contracting the three vertices of the triangle into a single vertex. Therefore, many definitions of snarks forbid triangles. However, although this requirement was also stated in
Gardner's
385:
If a graph contains a four-vertex cycle, it can be simplified in two different ways by removing two opposite edges of the cycle and replacing the resulting paths of degree-two vertices by single edges. It has a three-edge-coloring if and only if at least one of these simplifications does. Therefore,
275:
A list of all of the snarks up to 36 vertices (according to a strict definition), and up to 34 vertices (under a weaker definition), was generated by Gunnar
Brinkmann, Jan Goedgebeur, Jonas Hägglund and Klas Markström in 2012. The number of snarks for a given even number of vertices grows at least
496:. That is, he conjectured that the smallest snark, the Petersen graph, may be formed from any other snark by contracting some edges and deleting others. Equivalently (because the Petersen graph has maximum degree three) every snark has a subgraph that can be formed from the Petersen graph by
469:
conjectured that no snark could be embedded onto a surface in such a way that all faces are simple cycles and such that every two faces either are disjoint or share only a single edge; if any snark had such an embedding, its faces would form a cycle double cover. However, a counterexample to
464:
onto a surface in such a way that all faces of the embedding are simple cycles. When a cubic graph has a 3-edge-coloring, it has a cycle double cover consisting of the cycles formed by each pair of colors. Therefore, among cubic graphs, the snarks are the only possible counterexamples. More
453:). For the same reason that they have no Hamiltonian cycles, snarks have positive oddness: a completely even 2-factor would lead to a 3-edge-coloring, and vice versa. It is possible to construct infinite families of snarks whose oddness grows linearly with their numbers of vertices.
437:: when a cubic graph has a Hamiltonian cycle, it is always possible to 3-color its edges, by using two colors in alternation for the cycle, and the third color for the remaining edges. However, many known snarks are close to being Hamiltonian, in the sense that they are
386:
Isaacs requires a "nontrivial" cubic class-two graph to avoid four-vertex cycles, and other authors have followed suit in forbidding these cycles. The requirement that a snark avoid cycles of length four or less can be summarized by stating that the
271:
requiring six colors. However, because it contains a triangle, it is not generally considered a snark. Under strict definitions of snarks, the smallest snarks are the
Petersen graph and Blanuša snarks, followed by six different 20-vertex snarks.
125:), one encounters an interesting but somewhat mysterious variety of graphs called snarks. In spite of their simple definition...and over a century long investigation, their properties and structure are largely unknown.
1380:
248:
and the
Szekeres snark. Isaacs also discovered a 30-vertex snark that does not belong to the Blanuša–Descartes–Szekeres family and that is not a flower snark: the
309:
329:
681:
520:
announced a proof of this conjecture. Steps towards this result have been published in 2016 and 2019, but the complete proof remains unpublished. See the
426:, which are cubic and planar, and vice versa. A planar snark would therefore necessarily be dual to a counterexample to the four-color theorem. Thus, the
1528:
1473:
1146:
1129:
985:
1363:
908:
Graph theory and its
Applications: East and West, Proceedings of the First China–USA International Conference held in Jinan, June 9–20, 1986
1395:
Kochol, Martin (2010), "Complexity of 3-edge-coloring in the class of cubic graphs with a polyhedral embedding in an orientable surface",
460:
posits that in every bridgeless graph one can find a collection of cycles covering each edge twice, or equivalently that the graph can be
1067:
550:
465:
generally, snarks form the difficult case for this conjecture: if it is true for snarks, it is true for all graphs. In this connection,
276:
exponentially in the number of vertices. (Because they have odd-degree vertices, all snarks must have an even number of vertices by the
109:
521:
1208:
868:
1247:
944:
264:
80:
with only three colors. In order to avoid trivial cases, snarks are often restricted to have additional requirements on their
1515:
1291:
1195:, Contemporary Mathematics, vol. 98, With the collaboration of J. Koch., Providence, RI: American Mathematical Society,
505:
457:
145:
of snarks; its proof has been long announced but remains unpublished, and would settle a special case of the existence of
449:
of a cubic graph is defined as the minimum number of odd cycles, in any system of cycles that covers each vertex once (a
402:
Although these definitions only consider constraints on the girth up to five, snarks with arbitrarily large girth exist.
1523:
1519:
1461:
1457:
1431:
863:
517:
513:
497:
237:
910:, Annals of the New York Academy of Sciences, vol. 576, New York: New York Academy of Sciences, pp. 606–622,
1640:
948:
81:
983:
Brinkmann, Gunnar; Goedgebeur, Jan; Hägglund, Jonas; Markström, Klas (2012), "Generation and properties of snarks",
1346:
Jaeger, François (1985), "A survey of the cycle double cover conjecture", in
Alspach, B. R.; Godsil, C. D. (eds.),
527:
Tutte also conjectured a generalization to arbitrary graphs: every bridgeless graph with no
Petersen minor has a
771:
163:
107:
in 1976. Beyond coloring, snarks also have connections to other hard problems in graph theory: writing in the
1645:
1635:
1630:
1065:
Lukot'ka, Robert; Máčajová, Edita; Mazák, Ján; Škoviera, Martin (2015), "Small snarks with large oddness",
22:
1037:
1242:
438:
356:
607:
493:
419:
387:
85:
1042:
6th Czech-Slovak
International Symposium on Combinatorics, Graph Theory, Algorithms and Applications
414:
is true if and only if every snark is non-planar. This theorem states that every planar graph has a
450:
367:
348:
676:
441:: the removal of any single vertex leaves a Hamiltonian subgraph. A hypohamiltonian snark must be
1563:
1537:
1498:
1272:
1222:
1102:
1076:
1020:
994:
927:
885:
804:
788:
720:
643:
623:
595:
528:
501:
427:
411:
176:
146:
118:
92:
466:
1603:
1359:
1204:
766:
737:
509:
434:
379:
360:
277:
260:
249:
244:
and the Blanuša–Descartes–Szekeres snarks, a family that includes the two Blanuša snarks, the
207:
203:
122:
1465:
1547:
1482:
1404:
1351:
1300:
1256:
1196:
1155:
1086:
1045:
1004:
911:
877:
833:
780:
712:
655:
615:
559:
69:
1559:
1494:
1418:
1333:
1314:
1268:
1218:
1169:
1098:
1016:
923:
800:
753:
573:
418:
of its the vertices with four colors, but Tait showed how to convert 4-vertex-colorings of
1555:
1490:
1414:
1329:
1310:
1264:
1214:
1165:
1094:
1012:
919:
866:(1975), "Infinite families of non-trivial trivalent graphs which are not Tait-colorable",
821:
796:
749:
672:
569:
461:
245:
229:
214:
188:
103:'s work on the four color theorem in 1880, but their name is much newer, given to them by
504:, because any graph containing the Petersen graph as a minor must be nonplanar. In 1999,
268:
611:
594:(1976), "Snarks, boojums, and other conjectures related to the four-color-map theorem",
291:
1581:
1186:
915:
619:
591:
478:
415:
314:
225:
184:
158:
138:
104:
33:
1355:
1305:
473:
Determining whether a given cyclically 5-connected cubic graph is 3-edge-colorable is
117:
In the study of various important and difficult problems in graph theory (such as the
1624:
1435:
1276:
1182:
931:
808:
724:
344:
253:
172:
171:. However, the study of this class of graphs is significantly older than their name.
168:
100:
77:
1567:
1260:
1024:
359:, an edge whose removal would disconnect it, then it cannot be of class one. By the
1502:
1226:
1106:
700:
371:
340:
241:
192:
180:
96:
61:
45:
1190:
1378:
Kochol, Martin (2009), "Polyhedral embeddings of snarks in orientable surfaces",
398:
girth five or more and class two; they define a "weak snark" to allow girth four.
1119:
489:
474:
142:
130:
73:
57:
1551:
1486:
1049:
1008:
339:
The precise definition of snarks varies among authors, but generally refers to
240:
generalized Blanuša's method to construct two infinite families of snarks: the
1409:
903:
838:
659:
445:: the removal of any two vertices leaves a three-edge-colorable subgraph. The
423:
218:
1612:
1044:, Electronic Notes in Discrete Mathematics, vol. 28, pp. 417–424,
951:[Some remarks on the problem of map coloring on one-sided surfaces]
28:
1607:
1160:
716:
40:
949:"Einige Bemerkungen zum Problem des Kartenfärbens auf einseitigen Flächen"
191:
in 1898, although it had already been studied for a different purpose by
627:
524:
for other problems and results relating graph coloring to graph minors.
1200:
889:
792:
548:
ChladnĂ˝, Miroslav; Ĺ koviera, Martin (2010), "Factorisation of snarks",
390:
of these graphs, the length of their shortest cycles, is at least five.
1289:
Steffen, E. (1998), "Classification and characterizations of snarks",
881:
784:
394:
1542:
1350:, North-Holland Mathematics Studies, vol. 27, pp. 1–12,
1090:
1081:
999:
267:
discovered in 1910, it forms the boundary of a subdivision of the
39:
27:
21:
This article is about a term in graph theory. For other uses, see
564:
281:
175:
initiated the study of snarks in 1880, when he proved that the
902:
Watkins, John J. (1989), "Snarks", in
Capobianco, Michael F.;
161:
in 1976, after the mysterious and elusive object of the poem
378:
work giving the name "snark" to these graphs, Gardner lists
1123:
285:
705:
492:
conjectured that every snark has the Petersen graph as a
259:
Another notable cubic non-three-edge-colorable graph is
703:(1886), "A memoir on the theory of mathematical form",
477:. Therefore, determining whether a graph is a snark is
1144:
Kochol, Martin (1996), "Snarks without small cycles",
1040:(2007), "Exponentially many hypohamiltonian snarks",
824:(1973), "Polyhedral decompositions of cubic graphs",
317:
294:
1348:
Annals of Discrete Mathematics 27: Cycles in Graphs
157:Snarks were so named by the American mathematician
470:GrĂĽnbaum's conjecture was found by Martin Kochol.
430:also demonstrates that all snarks are non-planar.
343:(having exactly three edges at each vertex) whose
323:
303:
113:, Miroslav ChladnĂ˝ and Martin Ĺ koviera state that
1381:Proceedings of the American Mathematical Society
500:. This conjecture is a strengthened form of the
179:is equivalent to the statement that no snark is
1466:"Three-edge-colouring doublecross cubic graphs"
826:Bulletin of the Australian Mathematical Society
374:, graphs without loops or multiple adjacencies.
183:. The first graph known to be a snark was the
115:
1445:, Cambridge University Press, pp. 201–222
382:, which contains a triangle, as being a snark.
648:Proceedings of the Royal Society of Edinburgh
646:(1880), "Remarks on the colourings of maps",
288:contains the number of non-trivial snarks of
8:
1320:Steffen, E. (2001), "On bicritical snarks",
1237:
1235:
1526:(2019), "Excluded minors in cubic graphs",
1436:"Recent excluded minor theorems for graphs"
740:(1946), "Le problème des quatre couleurs",
410:Work by Peter G. Tait established that the
1060:
1058:
428:subsequent proof of the four-color theorem
1541:
1529:Journal of Combinatorial Theory, Series B
1474:Journal of Combinatorial Theory, Series B
1408:
1304:
1245:(2012), "The continuing saga of snarks",
1159:
1147:Journal of Combinatorial Theory, Series B
1130:On-Line Encyclopedia of Integer Sequences
1080:
998:
986:Journal of Combinatorial Theory, Series B
837:
742:Glasnik MatematiÄŤko-FiziÄŤki i Astronomski
586:
584:
582:
563:
316:
293:
1456:Edwards, Katherine; Sanders, Daniel P.;
858:
856:
854:
852:
850:
848:
978:
976:
974:
972:
970:
540:
18:3-regular graph with no 3-edge-coloring
638:
636:
393:More strongly, the definition used by
206:(two with 18 vertices), discovered by
129:As well as the problems they mention,
7:
906:; Hsu, D. Frank; Tian, Feng (eds.),
52:is one of six snarks on 20 vertices.
1384:, vol. 137, pp. 1613–1619
1068:Electronic Journal of Combinatorics
551:Electronic Journal of Combinatorics
110:Electronic Journal of Combinatorics
99:. Research on snarks originated in
91:One of the equivalent forms of the
1192:Every Planar Map is Four-Colorable
916:10.1111/j.1749-6632.1989.tb16441.x
682:L'Intermédiaire des Mathématiciens
620:10.1038/scientificamerican0476-126
14:
869:The American Mathematical Monthly
187:; it was proved to be a snark by
1580:DeVos, Matthew (March 7, 2007),
198:The next four known snarks were
88:. Infinitely many snarks exist.
1261:10.4169/college.math.j.43.1.082
1248:The College Mathematics Journal
422:into 3-edge-colorings of their
265:Heinrich Franz Friedrich Tietze
1443:Surveys in Combinatorics, 1999
769:(1948), "Network-colourings",
217:(210 vertices), discovered by
74:exactly three edges per vertex
1:
1356:10.1016/S0304-0208(08)72993-1
1306:10.1016/S0012-365X(97)00255-0
498:subdividing some of its edges
458:cycle double cover conjecture
311:vertices for small values of
228:(50 vertices), discovered by
1397:Discrete Applied Mathematics
347:with only three colors. By
1662:
1552:10.1016/j.jctb.2019.02.002
1487:10.1016/j.jctb.2015.12.006
1120:Sloane, N. J. A.
1050:10.1016/j.endm.2007.01.059
1009:10.1016/j.jctb.2013.05.001
137:concerns the existence of
86:the length of their cycles
20:
1410:10.1016/j.dam.2010.06.019
839:10.1017/S0004972700042660
677:"Sur le théorème de Tait"
660:10.1017/S0370164600044643
95:is that every snark is a
772:The Mathematical Gazette
256:was discovered in 1989.
164:The Hunting of the Snark
1124:"Sequence A130315"
395:Brinkmann et al. (2012)
355:If a cubic graph has a
345:edges cannot be colored
263:, with 12 vertices; as
78:edges cannot be colored
1243:belcastro, sarah-marie
1161:10.1006/jctb.1996.0032
717:10.1098/rstl.1886.0002
439:hypohamiltonian graphs
325:
305:
127:
53:
37:
36:is the smallest snark.
23:Snark (disambiguation)
420:maximal planar graphs
326:
306:
43:
31:
1292:Discrete Mathematics
315:
292:
153:History and examples
147:nowhere zero 4-flows
1586:Open Problem Garden
1582:"4-flow conjecture"
644:Tait, Peter Guthrie
612:1976SciAm.234d.126G
600:Scientific American
529:nowhere zero 4-flow
522:Hadwiger conjecture
433:All snarks are non-
121:conjecture and the
1641:Graph minor theory
1604:Weisstein, Eric W.
767:Descartes, Blanche
596:Mathematical Games
502:four color theorem
412:four-color theorem
321:
304:{\displaystyle 2n}
301:
177:four color theorem
119:cycle double cover
93:four color theorem
54:
38:
1403:(16): 1856–1860,
1365:978-0-444-87803-8
1133:, OEIS Foundation
1075:(1), Paper 1.51,
1038:Skupień, Zdzisław
957:DMV Annual Report
510:Daniel P. Sanders
361:handshaking lemma
324:{\displaystyle n}
278:handshaking lemma
250:double-star snark
123:5-flow conjecture
1653:
1617:
1616:
1589:
1588:
1577:
1571:
1570:
1545:
1512:
1506:
1505:
1470:
1453:
1447:
1446:
1440:
1428:
1422:
1421:
1412:
1392:
1386:
1385:
1375:
1369:
1368:
1343:
1337:
1336:
1317:
1308:
1299:(1–3): 183–203,
1286:
1280:
1279:
1239:
1230:
1229:
1201:10.1090/conm/098
1179:
1173:
1172:
1163:
1141:
1135:
1134:
1116:
1110:
1109:
1084:
1062:
1053:
1052:
1034:
1028:
1027:
1002:
980:
965:
964:
954:
945:Tietze, Heinrich
941:
935:
934:
899:
893:
892:
860:
843:
842:
841:
822:Szekeres, George
818:
812:
811:
763:
757:
756:
734:
728:
727:
697:
691:
690:
673:Petersen, Julius
669:
663:
662:
640:
631:
630:
606:(234): 126–130,
588:
577:
576:
567:
545:
485:Snark conjecture
349:Vizing's theorem
330:
328:
327:
322:
310:
308:
307:
302:
252:. The 50-vertex
135:snark conjecture
97:non-planar graph
70:undirected graph
1661:
1660:
1656:
1655:
1654:
1652:
1651:
1650:
1621:
1620:
1602:
1601:
1598:
1593:
1592:
1579:
1578:
1574:
1516:Robertson, Neil
1514:
1513:
1509:
1468:
1455:
1454:
1450:
1438:
1430:
1429:
1425:
1394:
1393:
1389:
1377:
1376:
1372:
1366:
1345:
1344:
1340:
1319:
1288:
1287:
1283:
1241:
1240:
1233:
1211:
1187:Haken, Wolfgang
1181:
1180:
1176:
1143:
1142:
1138:
1118:
1117:
1113:
1064:
1063:
1056:
1036:
1035:
1031:
982:
981:
968:
952:
943:
942:
938:
901:
900:
896:
882:10.2307/2319844
862:
861:
846:
820:
819:
815:
785:10.2307/3610702
765:
764:
760:
738:Blanuša, Danilo
736:
735:
731:
699:
698:
694:
671:
670:
666:
642:
641:
634:
592:Gardner, Martin
590:
589:
580:
547:
546:
542:
537:
487:
467:Branko GrĂĽnbaum
408:
337:
313:
312:
290:
289:
246:Descartes snark
230:George Szekeres
215:Descartes snark
189:Julius Petersen
155:
139:Petersen graphs
51:
26:
19:
12:
11:
5:
1659:
1657:
1649:
1648:
1646:Regular graphs
1643:
1638:
1636:Graph coloring
1633:
1631:Graph families
1623:
1622:
1619:
1618:
1597:
1596:External links
1594:
1591:
1590:
1572:
1507:
1448:
1423:
1387:
1370:
1364:
1338:
1328:(2): 141–150,
1281:
1231:
1209:
1183:Appel, Kenneth
1174:
1136:
1111:
1054:
1029:
993:(4): 468–488,
966:
936:
894:
876:(3): 221–239,
844:
832:(3): 367–387,
813:
779:(299): 67–69,
758:
729:
692:
664:
632:
578:
539:
538:
536:
533:
506:Neil Robertson
486:
483:
479:co-NP-complete
416:graph coloring
407:
404:
400:
399:
391:
383:
380:Tietze's graph
375:
364:
336:
333:
320:
300:
297:
261:Tietze's graph
234:
233:
226:Szekeres snark
222:
211:
208:Danilo Blanuša
204:Blanuša snarks
185:Petersen graph
159:Martin Gardner
154:
151:
105:Martin Gardner
49:
34:Petersen graph
17:
13:
10:
9:
6:
4:
3:
2:
1658:
1647:
1644:
1642:
1639:
1637:
1634:
1632:
1629:
1628:
1626:
1615:
1614:
1609:
1605:
1600:
1599:
1595:
1587:
1583:
1576:
1573:
1569:
1565:
1561:
1557:
1553:
1549:
1544:
1539:
1535:
1531:
1530:
1525:
1524:Thomas, Robin
1521:
1520:Seymour, Paul
1517:
1511:
1508:
1504:
1500:
1496:
1492:
1488:
1484:
1480:
1476:
1475:
1467:
1463:
1462:Thomas, Robin
1459:
1458:Seymour, Paul
1452:
1449:
1444:
1437:
1433:
1432:Thomas, Robin
1427:
1424:
1420:
1416:
1411:
1406:
1402:
1398:
1391:
1388:
1383:
1382:
1374:
1371:
1367:
1361:
1357:
1353:
1349:
1342:
1339:
1335:
1331:
1327:
1323:
1322:Math. Slovaca
1316:
1312:
1307:
1302:
1298:
1294:
1293:
1285:
1282:
1278:
1274:
1270:
1266:
1262:
1258:
1254:
1250:
1249:
1244:
1238:
1236:
1232:
1228:
1224:
1220:
1216:
1212:
1210:0-8218-5103-9
1206:
1202:
1198:
1194:
1193:
1188:
1184:
1178:
1175:
1171:
1167:
1162:
1157:
1153:
1149:
1148:
1140:
1137:
1132:
1131:
1125:
1121:
1115:
1112:
1108:
1104:
1100:
1096:
1092:
1091:10.37236/3969
1088:
1083:
1078:
1074:
1070:
1069:
1061:
1059:
1055:
1051:
1047:
1043:
1039:
1033:
1030:
1026:
1022:
1018:
1014:
1010:
1006:
1001:
996:
992:
988:
987:
979:
977:
975:
973:
971:
967:
962:
958:
950:
946:
940:
937:
933:
929:
925:
921:
917:
913:
909:
905:
898:
895:
891:
887:
883:
879:
875:
871:
870:
865:
864:Isaacs, Rufus
859:
857:
855:
853:
851:
849:
845:
840:
835:
831:
827:
823:
817:
814:
810:
806:
802:
798:
794:
790:
786:
782:
778:
774:
773:
768:
762:
759:
755:
751:
747:
743:
739:
733:
730:
726:
722:
718:
714:
710:
706:
702:
696:
693:
688:
684:
683:
678:
674:
668:
665:
661:
657:
653:
649:
645:
639:
637:
633:
629:
625:
621:
617:
613:
609:
605:
601:
597:
593:
587:
585:
583:
579:
575:
571:
566:
561:
557:
553:
552:
544:
541:
534:
532:
530:
525:
523:
519:
515:
511:
507:
503:
499:
495:
491:
484:
482:
480:
476:
471:
468:
463:
459:
454:
452:
448:
444:
440:
436:
431:
429:
425:
421:
417:
413:
405:
403:
396:
392:
389:
384:
381:
376:
373:
372:simple graphs
369:
365:
362:
358:
354:
353:
352:
350:
346:
342:
334:
332:
318:
298:
295:
287:
283:
279:
273:
270:
266:
262:
257:
255:
254:Watkins snark
251:
247:
243:
242:flower snarks
239:
231:
227:
223:
220:
216:
212:
209:
205:
201:
200:
199:
196:
194:
190:
186:
182:
178:
174:
173:Peter G. Tait
170:
169:Lewis Carroll
166:
165:
160:
152:
150:
148:
144:
140:
136:
132:
126:
124:
120:
114:
112:
111:
106:
102:
101:Peter G. Tait
98:
94:
89:
87:
83:
79:
75:
71:
67:
63:
59:
47:
42:
35:
30:
24:
16:
1611:
1585:
1575:
1533:
1527:
1510:
1478:
1472:
1451:
1442:
1426:
1400:
1396:
1390:
1379:
1373:
1347:
1341:
1325:
1321:
1296:
1290:
1284:
1255:(1): 82–87,
1252:
1246:
1191:
1177:
1154:(1): 34–47,
1151:
1145:
1139:
1127:
1114:
1072:
1066:
1041:
1032:
990:
984:
960:
956:
939:
907:
904:Guan, Mei Gu
897:
873:
867:
829:
825:
816:
776:
770:
761:
745:
741:
732:
708:
704:
701:Kempe, A. B.
695:
686:
680:
667:
651:
647:
603:
599:
565:10.37236/304
555:
549:
543:
526:
518:Robin Thomas
514:Paul Seymour
488:
472:
455:
446:
442:
432:
409:
401:
341:cubic graphs
338:
274:
269:Möbius strip
258:
238:Rufus Isaacs
235:
221:in 1948, and
197:
193:Alfred Kempe
162:
156:
143:graph minors
134:
128:
116:
108:
90:
82:connectivity
65:
62:graph theory
58:mathematical
55:
46:flower snark
15:
1536:: 219–285,
744:, Ser. II,
490:W. T. Tutte
475:NP-complete
435:Hamiltonian
424:dual graphs
131:W. T. Tutte
1625:Categories
535:References
443:bicritical
406:Properties
335:Definition
219:Bill Tutte
1613:MathWorld
1543:1403.2118
1481:: 66–95,
1277:118189042
1082:1212.3641
1000:1206.6690
963:: 155–159
932:222072657
809:250434686
748:: 31–42,
725:108716533
689:: 225–227
284:sequence
236:In 1975,
195:in 1886.
60:field of
1568:16237685
1464:(2016),
1434:(1999),
1189:(1989),
1025:15284747
947:(1910),
711:: 1–70,
675:(1898),
628:24950334
462:embedded
451:2-factor
232:in 1973.
210:in 1946,
1608:"Snark"
1560:3979232
1503:2656843
1495:3486338
1419:2679785
1334:1841443
1315:1630478
1269:2875562
1227:8735627
1219:1025335
1170:1385382
1122:(ed.),
1107:4805178
1099:3336565
1017:3071376
924:1110857
890:2319844
801:0026309
793:3610702
754:0026310
654:: 729,
608:Bibcode
574:2595492
558:: R32,
447:oddness
286:A130315
84:and on
56:In the
1566:
1558:
1501:
1493:
1417:
1362:
1332:
1313:
1275:
1267:
1225:
1217:
1207:
1168:
1105:
1097:
1023:
1015:
930:
922:
888:
807:
799:
791:
752:
723:
626:
572:
516:, and
357:bridge
181:planar
76:whose
68:is an
1564:S2CID
1538:arXiv
1499:S2CID
1469:(PDF)
1439:(PDF)
1273:S2CID
1223:S2CID
1103:S2CID
1077:arXiv
1021:S2CID
995:arXiv
953:(PDF)
928:S2CID
886:JSTOR
805:S2CID
789:JSTOR
721:S2CID
624:JSTOR
494:minor
388:girth
72:with
66:snark
1360:ISBN
1205:ISBN
1128:The
456:The
368:loop
282:OEIS
224:the
213:the
202:the
64:, a
44:The
32:The
1548:doi
1534:138
1483:doi
1479:119
1405:doi
1401:158
1352:doi
1301:doi
1297:188
1257:doi
1197:doi
1156:doi
1087:doi
1046:doi
1005:doi
991:103
912:doi
878:doi
834:doi
781:doi
713:doi
709:177
656:doi
616:doi
560:doi
280:.)
167:by
141:as
133:'s
1627::
1610:,
1606:,
1584:,
1562:,
1556:MR
1554:,
1546:,
1532:,
1522:;
1518:;
1497:,
1491:MR
1489:,
1477:,
1471:,
1460:;
1441:,
1415:MR
1413:,
1399:,
1358:,
1330:MR
1326:51
1324:,
1318:;
1311:MR
1309:,
1295:,
1271:,
1265:MR
1263:,
1253:43
1251:,
1234:^
1221:,
1215:MR
1213:,
1203:,
1185:;
1166:MR
1164:,
1152:67
1150:,
1126:,
1101:,
1095:MR
1093:,
1085:,
1073:22
1071:,
1057:^
1019:,
1013:MR
1011:,
1003:,
989:,
969:^
961:19
959:,
955:,
926:,
920:MR
918:,
884:,
874:82
872:,
847:^
828:,
803:,
797:MR
795:,
787:,
777:32
775:,
750:MR
719:,
707:,
685:,
679:,
652:10
650:,
635:^
622:,
614:,
602:,
598:,
581:^
570:MR
568:,
556:17
554:,
512:,
508:,
481:.
366:A
331:.
149:.
1550::
1540::
1485::
1407::
1354::
1303::
1259::
1199::
1158::
1089::
1079::
1048::
1007::
997::
914::
880::
836::
830:8
783::
746:1
715::
687:5
658::
618::
610::
604:4
562::
319:n
299:n
296:2
50:5
48:J
25:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
