363:, an embedding of a graph on a surface in such a way that every face is a simple cycle and every two faces that intersect do so in either a single vertex or a single edge. (In the case of a cubic graph, this can be simplified to a requirement that every two faces that intersect do so in a single edge.) Thus, in view of the reduction of the cycle double cover conjecture to snarks, it is of interest to investigate polyhedral embeddings of snarks. Unable to find such embeddings,
215:. Thus, every minimal counterexample must be cubic. But if a cubic graph can have its edges 3-colored (say with the colors red, blue, and green), then the subgraph of red and blue edges, the subgraph of blue and green edges, and the subgraph of red and green edges each form a collection of disjoint cycles that together cover all edges of the graph twice. Therefore, every minimal counterexample must be a non-3-edge-colorable bridgeless cubic graph, that is, a snark.
47:
210:
has four or more incident edges, one may “split off” two of those edges by removing them from the graph and replacing them by a single edge connecting their two other endpoints, while preserving the bridgelessness of the resulting graph. Again, a double cover of the resulting graph may be extended in
144:
undirected graph has a collection of cycles such that each edge of the graph is contained in exactly two of the cycles. The requirement that the graph be bridgeless is an obvious necessary condition for such a set of cycles to exist, because a bridge cannot belong to any cycle. A collection of cycles
205:
to the cycle double cover conjecture, all vertices must have three or more incident edges. For, a vertex with only one edge incident forms a bridge, while if two edges are incident on a vertex, one can contract them to form a smaller graph such that any double cover of the smaller graph extends to
293:
onto the manifold, in that every face of the embedding is a simple cycle in the graph. However, a cycle double cover of a graph with degree greater than three may not correspond to an embedding on a manifold: the cell complex formed by the cycles of the cover may have non-manifold topology at its
252:
of reducible configurations there is a number Îł such that all configurations in the set contain a cycle of length at most Îł. However, there exist snarks with arbitrarily high girth, that is, with arbitrarily high bounds on the length of their shortest cycle. A snark
347:
of the cycles in the cover have also been considered. The strongest of these is a conjecture that every bridgeless graph has a circular embedding on an orientable manifold in which the faces can be 5-colored. If true, this would imply a conjecture of
231:
will replace the triangle by a single vertex; any cycle double cover of the smaller graph can be extended back to a cycle double cover of the original cubic graph. Therefore, a minimal counterexample to the cycle double cover conjecture must be a
240:
which contain triangles. Through computer searches, it is known that every cycle of length 11 or less in a cubic graph forms a reducible configuration, and therefore that any minimal counterexample to the cycle double cover conjecture must have
328:. In terms of the cycle double cover conjecture, this is equivalent to the conjecture that there exists a cycle double cover, and an orientation for each of the cycles in the cover, such that for every edge
248:
Unfortunately, it is not possible to prove the cycle double cover conjecture using a finite set of reducible configurations. Every reducible configuration contains a cycle, so for every finite set
227:, a subgraph that can be replaced by a smaller subgraph in a way that would preserve the existence or nonexistence of a cycle double cover. For instance, if a cubic graph contains a triangle, a
309:
For cubic graphs, 2-vertex-connectedness and bridgelessness are equivalent. Therefore, the circular embedding conjecture is clearly at least as strong as the cycle double cover conjecture.
211:
a straightforward way to a double cover of the original graph: every cycle of the split off graph corresponds either to a cycle of the original graph, or to a pair of cycles meeting at
324:
A stronger version of the circular embedding conjecture that has also been considered is the conjecture that every 2-vertex-connected graph has a circular embedding on an
195:
4). It turns out that snarks form the only difficult case of the cycle double cover conjecture: if the conjecture is true for snarks, it is true for any graph.
223:
One possible attack on the cycle double cover problem would be to show that there cannot exist a minimum counterexample, by proving that any graph contains a
882:
175:
is a special case of a bridgeless graph, having the additional properties that every vertex has exactly three incident edges (that is, the graph is
40:
791:
769:
613:
549:
691:
824:
872:
706:
564:
306:
has a circular embedding onto a manifold. If so, the graph also has a cycle double cover, formed by the faces of the embedding.
312:
If a circular embedding exists, it might not be on a surface of minimal genus: Nguyen Huy Xuong described a 2-vertex-connected
157:
can only be covered by using the same cycle more than once, so this sort of duplication is allowed in a cycle double cover.
867:
679:
109:
503:
Fleischner, Herbert (1976), "Eine gemeinsame Basis fĂĽr die
Theorie der Eulerschen Graphen und den Satz von Petersen",
779:
753:
646:
Kochol, Martin (2009a), "3-Regular non 3-edge-colorable graphs with polyhedral embeddings in orientable surfaces",
303:
536:, Lecture Notes in Computer Science (Ausiello, G., Böhm, C. (eds)), vol. 62, Springer, pp. 289–299,
141:
93:
that represents the graph provide a double cover of the graph: each edge belongs to exactly two faces.
811:
877:
242:
172:
166:
78:
233:
188:
807:
277:
If a graph has a cycle double cover, the cycles of the cover can be used to form the 2-cells of a
520:
844:
364:
840:
787:
765:
700:
687:
609:
558:
545:
353:
237:
90:
59:
17:
727:
665:
632:
601:
582:
537:
512:
228:
180:
117:
86:
82:
55:
828:
821:
715:
278:
192:
125:
105:
815:
37:
Does every bridgeless graph have a multiset of cycles covering every edge exactly twice?
832:
758:
384:
344:
313:
202:
51:
605:
587:
46:
861:
524:
325:
184:
573:
Huck, A. (2000), "Reducible configurations for the cycle double cover conjecture",
282:
154:
97:
67:
670:
656:
Kochol, Martin (2009b), "Polyhedral embeddings of snarks in orientable surfaces",
375:) disproved GrĂĽnbaum's conjecture by finding a snark with a polyhedral embedding.
85:
that together include each edge of the graph exactly twice. For instance, for any
741:
349:
176:
150:
101:
70:
732:
257:
with girth greater than Îł cannot contain any of the configurations in the set
140:
The usual formulation of the cycle double cover conjecture asks whether every
121:
541:
179:) and that it is not possible to partition the edges of the graph into three
849:
637:
145:
satisfying the condition of the cycle double cover conjecture is called a
286:
516:
29:
650:, Lecture Notes in Computer Science, vol. 5417, pp. 319–323
596:
Jaeger, F. (1985), "A survey of the cycle double cover conjecture",
682:(1979), "Sums of circuits", in Bondy, J. A.; Murty, U.S.R. (eds.),
600:, North-Holland Mathematics Studies, vol. 27, pp. 1–12,
343:
Alternatively, strengthenings of the conjecture that involve
532:
Itai, A.; Rodeh, M. (1978), "Covering a graph by circuits",
359:
A stronger type of embedding than a circular embedding is a
285:. In the case of a cubic graph, this complex always forms a
206:
one of the original graph. On the other hand, if a vertex
746:
Personal correspondence with H. Fleischner (July 22,1987)
648:
Graph
Drawing 2008, Editors: I.G. Tollis, M. Patrignani
265:
are not strong enough to rule out the possibility that
623:
Kochol, Martin (1996), "Snarks without small cycles",
367:
conjectured that they do not exist, but Kochol (
718:(1973), "Polyhedral decomposition of cubic graphs",
598:
Annals of
Discrete Mathematics 27 – Cycles in Graphs
757:
316:none of whose circular embeddings lie on a torus.
658:Proceedings of the American Mathematical Society
534:Automata, Languages and Programming. ICALP 1978.
720:Bulletin of the Australian Mathematical Society
686:, New York: Academic Press, pp. 342–355,
8:
336:are oriented in opposite directions through
27:Cycles in a graph that cover each edge twice
128:, and in that context is also known as the
124:can equivalently be formulated in terms of
731:
669:
636:
625:Journal of Combinatorial Theory, Series B
586:
414:
320:Stronger conjectures and related problems
760:Integer Flows and Cycle Covers of Graphs
459:
457:
455:
453:
451:
449:
447:
426:
201:observes that, in any potential minimal
54:, corresponding to its embedding on the
45:
438:
395:
372:
368:
41:(more unsolved problems in mathematics)
698:
556:
487:
463:
198:
402:
7:
475:
269:might be a minimal counterexample.
352:that every bridgeless graph has a
25:
883:Unsolved problems in graph theory
822:The Cycle Double Cover Conjecture
236:, ruling out some snarks such as
845:"Cycle Double Cover Conjecture"
818:, from the Open Problem Garden.
684:Graph Theory and Related Topics
32:Unsolved problem in mathematics
786:, Cambridge University Press,
784:Circuit Double Cover of Graphs
120:has a cycle double cover. The
1:
812:circular embedding conjecture
808:Cycle double cover conjecture
705:: CS1 maint: date and year (
671:10.1090/S0002-9939-08-09698-6
664:(5) (5 ed.): 1613–1619,
606:10.1016/S0304-0208(08)72993-1
588:10.1016/S0166-218X(99)00126-2
563:: CS1 maint: date and year (
296:circular embedding conjecture
273:Circular embedding conjecture
183:(that is, the graph has no 3-
130:circular embedding conjecture
114:cycle double cover conjecture
18:Cycle double cover conjecture
575:Discrete Applied Mathematics
385:Petersen coloring conjecture
50:A cycle double cover of the
300:strong embedding conjecture
899:
505:Monatshefte fĂĽr Mathematik
332:the two cycles that cover
289:. The graph is said to be
164:
733:10.1017/S0004972700042660
631:(1) (1 ed.): 34–47,
873:Topological graph theory
542:10.1007/3-540-08860-1_21
304:2-vertex-connected graph
219:Reducible configurations
415:Itai & Rodeh (1978)
281:onto a two-dimensional
261:, so the reductions in
225:reducible configuration
638:10.1006/jctb.1996.0032
149:. Some graphs such as
63:
816:GrĂĽnbaum's conjecture
49:
868:Graph theory objects
361:polyhedral embedding
167:snark (graph theory)
354:nowhere-zero 5-flow
326:orientable manifold
291:circularly embedded
234:triangle-free graph
161:Reduction to snarks
77:is a collection of
841:Weisstein, Eric W.
827:2008-12-05 at the
517:10.1007/BF01387754
302:states that every
147:cycle double cover
104:, Itai and Rodeh,
75:cycle double cover
64:
793:978-0-5212-8235-2
771:978-0-8247-9790-4
615:978-0-444-87803-8
551:978-3-540-08860-8
181:perfect matchings
112:and known as the
91:convex polyhedron
89:, the faces of a
60:hemi-dodecahedron
16:(Redirected from
890:
854:
853:
796:
774:
763:
748:
736:
735:
710:
704:
696:
674:
673:
651:
641:
640:
618:
591:
590:
568:
562:
554:
527:
491:
485:
479:
473:
467:
461:
442:
436:
430:
424:
418:
412:
406:
400:
189:Vizing's theorem
126:graph embeddings
118:bridgeless graph
116:, whether every
98:unsolved problem
87:polyhedral graph
83:undirected graph
56:projective plane
33:
21:
898:
897:
893:
892:
891:
889:
888:
887:
858:
857:
839:
838:
829:Wayback Machine
804:
794:
780:Zhang, Cun-Quan
778:
772:
754:Zhang, Cun-Quan
752:
740:
714:
697:
694:
678:
655:
645:
622:
616:
595:
572:
555:
552:
531:
502:
499:
494:
486:
482:
474:
470:
462:
445:
437:
433:
427:Szekeres (1973)
425:
421:
413:
409:
401:
397:
393:
381:
365:Branko GrĂĽnbaum
322:
279:graph embedding
275:
221:
193:chromatic index
169:
163:
153:and bridgeless
138:
106:George Szekeres
68:graph-theoretic
44:
43:
38:
35:
31:
28:
23:
22:
15:
12:
11:
5:
896:
894:
886:
885:
880:
875:
870:
860:
859:
856:
855:
836:
833:Dan Archdeacon
819:
803:
802:External links
800:
799:
798:
792:
776:
770:
750:
738:
726:(3): 367–387,
712:
693:978-0121143503
692:
680:Seymour, P. D.
676:
653:
643:
620:
614:
593:
581:(1–3): 71–90,
570:
550:
529:
511:(4): 267–278,
498:
495:
493:
492:
480:
468:
443:
439:Seymour (1979)
431:
419:
407:
394:
392:
389:
388:
387:
380:
377:
321:
318:
314:toroidal graph
294:vertices. The
274:
271:
238:Tietze's graph
220:
217:
203:counterexample
162:
159:
137:
134:
52:Petersen graph
39:
36:
30:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
895:
884:
881:
879:
876:
874:
871:
869:
866:
865:
863:
852:
851:
846:
842:
837:
834:
830:
826:
823:
820:
817:
813:
809:
806:
805:
801:
795:
789:
785:
781:
777:
773:
767:
764:, CRC Press,
762:
761:
755:
751:
747:
743:
739:
734:
729:
725:
721:
717:
713:
708:
702:
695:
689:
685:
681:
677:
672:
667:
663:
659:
654:
649:
644:
639:
634:
630:
626:
621:
617:
611:
607:
603:
599:
594:
589:
584:
580:
576:
571:
566:
560:
553:
547:
543:
539:
535:
530:
526:
522:
518:
514:
510:
506:
501:
500:
496:
489:
488:Kochol (1996)
484:
481:
477:
472:
469:
465:
464:Jaeger (1985)
460:
458:
456:
454:
452:
450:
448:
444:
440:
435:
432:
428:
423:
420:
416:
411:
408:
404:
399:
396:
390:
386:
383:
382:
378:
376:
374:
370:
366:
362:
357:
355:
351:
346:
341:
339:
335:
331:
327:
319:
317:
315:
310:
307:
305:
301:
297:
292:
288:
284:
280:
272:
270:
268:
264:
260:
256:
251:
246:
245:at least 12.
244:
239:
235:
230:
229:Δ-Y transform
226:
218:
216:
214:
209:
204:
200:
199:Jaeger (1985)
196:
194:
190:
186:
185:edge coloring
182:
178:
174:
168:
160:
158:
156:
155:cactus graphs
152:
148:
143:
135:
133:
131:
127:
123:
119:
115:
111:
107:
103:
99:
94:
92:
88:
84:
80:
76:
72:
69:
61:
57:
53:
48:
42:
19:
848:
783:
759:
745:
742:Tutte, W. T.
723:
719:
716:Szekeres, G.
683:
661:
657:
647:
628:
624:
597:
578:
574:
533:
508:
504:
483:
471:
434:
422:
410:
403:Tutte (1987)
398:
360:
358:
342:
337:
333:
329:
323:
311:
308:
299:
295:
290:
283:cell complex
276:
266:
262:
258:
254:
249:
247:
224:
222:
212:
207:
197:
170:
151:cycle graphs
146:
139:
129:
113:
110:Paul Seymour
95:
74:
65:
878:Conjectures
476:Huck (2000)
350:W. T. Tutte
136:Formulation
102:W. T. Tutte
100:, posed by
71:mathematics
862:Categories
497:References
165:See also:
142:bridgeless
122:conjecture
850:MathWorld
525:118767538
345:colorings
187:, and by
96:It is an
825:Archived
782:(2012),
756:(1997),
744:(1987),
701:citation
559:citation
379:See also
287:manifold
814:, and
790:
768:
690:
612:
548:
523:
81:in an
79:cycles
521:S2CID
391:Notes
373:2009b
369:2009a
243:girth
177:cubic
173:snark
58:as a
788:ISBN
766:ISBN
707:link
688:ISBN
610:ISBN
565:link
546:ISBN
191:has
108:and
73:, a
728:doi
666:doi
662:137
633:doi
602:doi
583:doi
538:doi
513:doi
298:or
66:In
864::
847:,
843:,
831:,
810:,
722:,
703:}}
699:{{
660:,
629:67
627:,
608:,
579:99
577:,
561:}}
557:{{
544:,
519:,
509:81
507:,
446:^
371:,
356:.
340:.
171:A
132:.
835:.
797:.
775:.
749:.
737:.
730::
724:8
711:.
709:)
675:.
668::
652:.
642:.
635::
619:.
604::
592:.
585::
569:.
567:)
540::
528:.
515::
490:.
478:.
466:.
441:.
429:.
417:.
405:.
338:e
334:e
330:e
267:G
263:S
259:S
255:G
250:S
213:v
208:v
62:.
34::
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
