[1] Alon, N., and Tarsi, M. 1985. Covering multigraphs by simple circuits. SIAM J. Algebraic Discrete Methods, 6, 345–350.Google Scholar

[2] Alspach, B., and Godsil, C. 1985. Unsolved problems. Pages 461–467 of: Cycles in Graphs, Ann. Discrete Math., vol. 27. Amsterdam: North-Holland.

[3] Alspach, B., and Zhang, C.-Q. 1993. Cycle covers of cubic multigraphs. Discrete Math., 111, 11–17.Google Scholar

[4] Alspach, B., Goddyn, L. A., and Zhang, C.-Q. 1994. Graphs with the circuit cover property. Trans. Amer. Math. Soc., 344, 131–154.Google Scholar

[5] Appel, K., and Haken, W. 1977. Every map is four colorable, Part I: Discharging. Illinois J. Math., 21, 429–490.Google Scholar

[6] Appel, K., and Haken,W. 1989. Every Map is Four Colorable. Contemp. Math. AMS, vol. 98. Providence, RI: American Mathematical Society.

[7] Appel, K., Haken, W., and Koch, J. 1977. Every map is four colorable, Part II: Reducibility. Illinois J. Math., 21, 491–567.

[8] Archdeacon, D. 1984. Face coloring of embedded graphs. J. Graph Theory, 8, 387–398.Google Scholar

[9] Ash, P., and Jackson, B. 1984. Dominating cycles in bipartite graph. Pages 81–87 of: Bondy, J. A., and Murty, U. S. R. (eds), Progress in Graph Theory. New York: Academic Press.

[10] Barnette, D. W. 1996. Cycle covers of planar 3-connected graphs. J. Combin. Math. Combin. Comput., 20, 245–253.Google Scholar

[11] Berge, C. 1973. Graph and Hypergraph. New York: North-Holland. (translated by E. Minieka).

[12] Bermond, J. C., Jackson, B., and Jaeger, F. 1983. Shortest coverings of graphs with cycles. J. Combin. Theory Ser. B, 35, 297–308.Google Scholar

[13] Biggs, N. L., Lloyd, E. K., and Wilson, R. J. 1976. Graph Theory 1736–1936. Oxford: Clarendon Press.

[14] Blanuša, D. 1946. Problem ceteriju boja (The problem of four colors). Hrvatsko Prirodoslovno Društvo Glasnik Mat-Fiz. Astr, Ser. II, 1, 31–42.Google Scholar

[15] Bollobás, B. 1978. Extremal Graph Theory. London: Academic Press.

[16] Bondy, J. A. 1990. Small cycle double covers of graphs. Pages 21–40 of: Hahn, G., Sabidussi, G., and Woodrow, R. (eds), Cycles and Rays. NATO ASI Ser. C. Dordrecht: Kluwer Academic Publishers.

[17] Bondy, J. A., and Hell, P. 1990. A note on the star chromatic number. J. Graph Theory, 14, 479–482.Google Scholar

[18] Bondy, J. A., and Murty, U. S. R. 1976. Graph Theory with Applications. London: Macmillan.

[19] Bondy, J. A., and Murty, U. S. R. 2008. Graph Theory. Springer.

[20] Brinkmann, G., and Steffen, E. 1998. Snarks and reducibility. Ars Combin., 50, 292–296.Google Scholar

[21] Brinkmann, G., Goedgebeur, J., Hägglund, J., and Markström, K. 2011. Generation and properties of snarks. Preprint.

[22] Cai, L., and Corneil, D. 1992. On cycle double covers of line graphs. Discrete Math., 102, 103–106.Google Scholar

[23] Carroll, L. 1874. (C. L. Dodgson) The Hunting of the Snark (An Agony in 8 Fits). London: Macmillan.

[24] Catlin, P. A. 1988. A reduction method to find spanning eulerian subgraph. J. Graph Theory, 12, 29–45.Google Scholar

[25] Catlin, P. A. 1989. Double cycle covers and the Petersen graph. J. Graph Theory, 13, 465–483.Google Scholar

[26] Catlin, P. A. 1990. Double cycle covers and the Petersen graph, II. Congr. Numer., 76, 173–181.Google Scholar

[27] Catlin, P. A. 1992. Supereulerian graphs: a survey. J. Graph Theory, 16, 177–196.Google Scholar

[28] Catlin, P. A., Han, Z.-Y., and Lai, H.-J. 1996. Graphs without spanning closed trails. Discrete Math., 160, 81–91.Google Scholar

[29] Cavicchioli, A., Meschiari, M., Ruini, B., and Spaggiari, F. 1998. A survey on snarks and new results: products, reducibility and a computer Search. J. Graph Theory, 28, 57–86.Google Scholar

[30] Cavicchioli, A., Murgolo, T. E., Ruini, B., and Spaggiari, F. 2003. Special classes of snarks. Acta Applicandae Mathematicae, 76, 57–88.Google Scholar

[31] Celmins, U. A. 1984. On cubic graphs that do not have an edge 3-coloring. Ph.D. thesis, University of Waterloo, Ontario, Canada.

[32] Celmins, U. A., Fouquet, J. L., and Swart, E. R. 1980. Construction and characterization of snarks. Research Report, University of Waterloo, Ontario, Canada.

[33] Chan, M. 2009. A survey of the cycle double cover conjecture. Preprint, Princeton University.

[34] Chartrand, G., and Lesniak, L. 1986. Graphs and Digraphs. Second edn. Belmont, CA: Wadsworth and Brooks/Cole.

[35] Chen, C. C., and Quimpo, N. F. 1981. On strongly hamiltonian abelian group graphs. Pages 23–34 of: McAvaney, K. L. (ed), Combinatorial Mathematics VIII. Lecture Notes in Math., vol. 884. Berlin: Springer-Verlag.

[36] Chen, Z.-H., and Lai, H.-J. 1995. Reductions techniques for supereulerian graphs and related topics – a survey. Pages 53–69 of: Ku, T.-H. (ed), Combinatorics and Graph Theory 95. Singapore: World Scientific.

[37] Chetwynd, A. G., and Wilson, R. J. 1981. Snarks and supersnarks. Pages 215–241 of: The Theory and Applications of Graphs. New York: Wiley.

[38] Cutler, J., and Häggkvist, R. 2004. Cycle double covers of graphs with disconnected frames. Research report 6, Department of Mathematics, Umeå University, Sweden.

[39] Descartes, B. 1948. Network-colourings. Math. Gazette, 32, 67–69.Google Scholar

[40] DeVos, M., Johnson, T., and Seymour, P. D.Cut Coloring and Circuit Covering. Submitted for publication, http://www.math.princeton.edu/∼pds/papers/cutcolouring/.

[41] Diestel, R. 2010. Graph Theory. Fourth edn. Springer-Verlag.

[42] Ding, S.-K., Hoede, C., and Vestergaard, P. D. 1990. Strong cycle covers. Ars Combin., 29C, 130–139.Google Scholar

[43] Edmonds, J. 1965. Maximum matching and a polyhedron with (0, 1)- vertices. J. Res. Nat. Bur. Standards B, 69, 125–130.Google Scholar

[44] Edmonds, J., and Johnson, E. L. 1973. Matching, Euler tours and the Chinese postman. Mathematical Programming, 5, 88–124.Google Scholar

[45] Eisenberg, M. 1974. Topology. New York: Holt, Rinehart and Winston, Inc.

[46] Ellingham, M. N. 1984. Petersen subdivisions in some regular graphs. Congr. Numer., 44, 33–40.Google Scholar

[47] Ellingham, M. N., and Zha, X.-Y. 2011. Orientable embeddings and orientable cycle double covers of projective-planar graphs. European J. Combin., 32, 495–509.Google Scholar

[48] Esteva, E. G. M., and Jensen, T. R. 2007. On semiextensions and circuit double covers. J. Combin. Theory Ser. B, 97, 474–482.Google Scholar

[49] Esteva, E. G. M., and Jensen, T. R. 2009. A note on semiextensions of stable circuits. Discrete Math., 309, 4952–4954.Google Scholar

[50] Fan, G.-H. 1992. Covering graphs by cycles. SIAM J. Discrete Math., 5, 491–496.Google Scholar

[51] Fan, G.-H. 1994. Short cycle covers of cubic graphs. J. Graph Theory, 18, 131–141.Google Scholar

[52] Fan, G.-H. 1998. Proofs of two minimum circuit cover conjectures. J. Combin. Theory Ser. B, 74, 353–367.Google Scholar

[53] Fan, G.-H., and Raspaud, A. 1994. Fulkerson's conjecture and circuits covers. J. Combin. Theory Ser. B, 61, 133–138.Google Scholar

[54] Fan, G.-H., and Zhang, C.-Q. 2000. Circuit decompositions of eulerian graphs. J. Combin. Theory Ser. B, 78, 1–23.Google Scholar

[55] Fiorini, S., and Wilson, R. J. 1977. Edge colourings of graphs. Research Notes in Mathematics, vol. 16. Pitman.

[56] Fiorini, S., and Wilson, R. J. 1978. Edge colourings of graphs. Pages 103–126 of: Beineke, L. W., and Wilson, R. J. (eds), Selected Topics in Graph Theory. London: Academic Press.

[57] Fish, J. M., Klimmek, R., and Seyffarth, K. 2002. Line graphs of complete multipartite graphs have small cycle double covers. Discrete Math., 257, 39–61.Google Scholar

[58] Fleischner, H. 1976. Eine gemeinsame Basis für die Theorie der eulerschen Graphen und den Satz von Petersen. Monatsh. Math., 81, 267–278.Google Scholar

[59] Fleischner, H. 1980. Eulersche Linien und Kreisuberdeckungen die vorgegebene Duurchgange inden Kanten vermeiden. J. Combin. Theory Ser. B, 29, 145–167.Google Scholar

[60] Fleischner, H. 1983. Eulerian Graph. Pages 17–53 of: Beineke, L. W., and Wilson, R. J. (eds), Selected Topics in Graph Theory (2). London: Academic Press.

[61] Fleischner, H. 1984. Cycle decompositions, 2-coverings, removable cycles and the four-color disease. Pages 233–246 of: Bondy, J. A., and Murty, U. S. R. (eds), Progress in Graph Theory. New York: Academic Press.

[62] Fleischner, H. 1986. Proof of the strong 2-cover conjecture for planar graphs. J. Combin. Theory Ser. B, 40, 229–230.Google Scholar

[63] Fleischner, H. 1988. Some blood, sweat, but no tears in eulerian graph theory. Congr. Numer., 63, 9–48.Google Scholar

[64] Fleischner, H. 1990. Communication at Cycle Double Cover Conjecture Workshop, Barbados, February 25–March 4.

[65] Fleischner, H. 1991. Eulerian Graphs and Related Topics, Part 1, Vol. 2. Ann. Discrete Math., vol. 50. North-Holland.

[66] Fleischner, H. 1994. Uniqueness of maximal dominating cycles in 3- regular graphs and Hamiltonian cycles in 4-regular graphs. J. Graph Theory, 18, 449–459.Google Scholar

[67] Fleischner, H. 2002. Bipartizing matchings and Sabidussi's compatibility conjecture. Discrete Math., 244, 77–82.Google Scholar

[68] Fleischner, H. 2010. Uniquely hamiltonian (simple) graphs of minimum degree four. 8th French Combinatorial Conference, June 30th 2010. University Paris XI - Sud, Orsay, France.

[69] Fleischner, H. 2011. Personal communication, Vienna.

[70] Fleischner, H., and Frank, A. 1990. On cycle decomposition of eulerian graph. J. Combin. Theory Ser. B, 50, 245–253.Google Scholar

[71] Fleischner, H., and Fulmek, M. 1990. P(D)-compatible eulerian trails in digraphs and a new splitting lemma. Pages 291–303 of: Bodendiek, R. (ed), Contemporary Methods in Graph Theory.Google Scholar

[72] Fleischner, H., and Häggkvist, R. 2009. Circuit double covers in special types of cubic graphs. Discrete Math., 309, 5724–5728.Google Scholar

[73] Fleischner, H., and Kochol, M. 2002. A note about the dominating circuit conjecture. Discrete Math., 259, 307–309.Google Scholar

[74] Fleischner, H., Hilton, A. J. W., and Jackson, B. 1990. On the maximum number of pairwise compatible Euler cycles. J. Graph Theory, 14, 51–63.Google Scholar

[75] Fleischner, H., Genest, F., and Jackson, B. 2007. Compatible circuit decompositions of 4-regular graphs. J. Graph Theory, 56, 227–240.Google Scholar

[76] Ford, L. R., and Fulkerson, D. R. 1962. Flows in Networks. Princeton, NJ: Princeton University Press.

[77] Fouquet, J. 1982. Note sur la non existence d'un snark d'ordre 16. Discrete Math., 38, 163–171.Google Scholar

[78] Fowler, T. G. 1998. Unique Coloring of Planar Graphs. Ph.D. thesis, Georgia Tech.

[79] Franklin, P. 1941. The Four Color Problem. New York: Scripta Mathematica, Yeshiva College.

[80] Fulkerson, D. R. 1971. Blocking and antiblocking pairs of polyhedral. Math. Programming, 1, 168–194.Google Scholar

[81] Gardner, M. 1976. Mathematical Games. Scientific American, 4, 126–130.Google Scholar

[82] Goddyn, L. A. 1985. A girth requirement for the double cycle cover conjecture. Pages 13–26 of: Alspach, B., and Godsil, C. (eds), Cycles in Graphs. Ann. Discrete Math., vol. 27. Amsterdam: North-Holland.

[83] Goddyn, L. A. 1988. Cycle covers of graphs. Ph.D. thesis, University of Waterloo, Ontario, Canada.

[84] Goddyn, L. A. 1989. Cycle double covers of graphs with Hamilton paths. J. Combin. Theory Ser. B, 46, 253–254.Google Scholar

[85] Goddyn, L. A. 1991. Cycle double covers–current status and new approaches. Contributed lecture at Cycle Double Cover Conjecture Workshop, IINFORM, Vienna, January 1991.

[86] Goddyn, L. A. 1993. Cones, lattices and Hilbert bases of circuits and perfect matching. Contemporary Mathematics, 147, 419–440.Google Scholar

[87] Goddyn, L. A., van den Heuvel, J., and McGuinness, S. 1997. Removable circuits in multigraphs. J. Combin. Theory Ser. B, 71, 130–143.Google Scholar

[88] Goddyn, L. A., Tarsi, M., and Zhang, C.-Q. 1998. On (k, d)-colorings and fractional nowhere zero flows. J. Graph Theory, 28, 155–161.Google Scholar

[89] Goldwasser, J. L., and Zhang, C.-Q. 1996. On minimal counterexamples to a conjecture about unique edge-3-coloring. Congr. Numer., 113, 143–152.Google Scholar

[90] Goldwasser, J. L., and Zhang, C.-Q. 1999. Permutation graphs and Petersen graph. Ars Combin., 51, 240–248.Google Scholar

[91] Goldwasser, J. L., and Zhang, C.-Q. 2000. Uniquely edge-3-colorable graphs and snarks. Graph and Combinatorics, 16, 257–267.Google Scholar

[92] Gould, R. 1988. Graph Theory. Menlo Park, CA: Benjamin/Cummings Publishing Company, Inc.

[93] Greenwell, D., and Kronk, H. V. 1973. Uniquely line-colorable graphs. Canad. Math. Bull., 16, 525–529.Google Scholar

[94] Gross, J. L., and Tucker, T. W. 1987. Topological Graph Theory. New York: John Willey & Sons.

[95] Guan, M.-G., and Fleischner, H. 1985. On the minimum weighted cycle covering problem for planar graphs. Ars Combin., 20, 61–68.Google Scholar

[96] Gusfield, D. 1983. Connectivity and edge-disjoint spanning trees. Inform. Process. Lett., 16, 87–89.Google Scholar

[97] Haggard, G. 1977. Edmonds Characterization of disc embedding. Pages 291–302 of: Proceeding of the 8th Southeastern Conference of Combinatorics, Graph Theory and Computing, Utilitas Mathematica.

[98] Häggkvist, R. 2009. Lollipop Andrew strikes again (abstract). 22nd British Combinatorial Conference, July 5–10, 2009. University of St Andrews, UK.

[99] Häggkvist, R., and Markström, K. 2006a. Cycle double covers and spanning minors I. J. Combin. Theory Ser. B, 96, 183–206.Google Scholar

[100] Häggkvist, R., and Markström, K. 2006b. Cycle double covers and spanning minors II. Discrete Math., 306, 762–778.Google Scholar

[101] Häggkvist, R., and McGuinness, S. 2005. Double covers of cubic graphs with oddness 4. J. Combin. Theory Ser. B, 93, 251–277.Google Scholar

[102] Hägglund, J. 2011. Personal communication.

[103] Hägglund, J., and Markström, K. 2011. On stable cycles and the cycle double covers of graphs with large circumference. Discrete Math. doi:10.1016.j.disc.2011.08.024.

[104] Heawood, P. J. 1898. On the four-color map theorem. Quarterly J. Pure Math. Applied Math., 29, 270–285.Google Scholar

[105] Heinrich, K., Liu, J.-P., and Zhang, C.-Q. 1998. Triangle-free circuit decompositions and Petersen-minor. J. Combin. Theory Ser. B, 72, 197–207.Google Scholar

[106] Hind, H. R. 1988. Restricted edge-colourings, Chapter 5. Ph.D. thesis, Cambridge University, UK.

[107] Hoffman, A. J. 1958. Page 80 of Théorie des Graph (by C. Berge).

[108] Hoffman, A. J. 1960. Some recent applications of the theorem of linear inequalities to extremal combinatorial analysis. Proc. Symp. Appl. Math., 10, 113–127.Google Scholar

[109] Hoffman, F., Locke, S. C., and Meyerowitz, A. D. 1991. A note on cycle double cover in Cayley graphs. Mathematica Pannonica, 2, 63–66.Google Scholar

[110] Hoffmann-Ostenhof, A. 2007. A counterexample to the bipartizing matching conjecture. Discrete Math., 307, 2723–2733.Google Scholar

[111] Hoffmann-Ostenhof, A. 2012. Nowhere-zero flows and structures in cubic graphs. Ph.D. thesis, University of Vienna, Austria.

[112] Holton, D. A., and Sheehan, J. 1993. The Petersen Graph. Australian Mathematical Society Lecture Series, vol. 7. Cambridge University Press.

[113] Holyer, I. 1981. The NP-completeness of edge-coloring. SIAM J. Comput., 10, 718–720.Google Scholar

[114] Huck, A. 1993. On cycle-double covers of bridgeless graphs with hamiltonian paths. Tech. rept. 254. Institute of Mathematics, University of Hannover, Germany.

[115] Huck, A. 2000. Reducible configurations for the cycle double cover conjecture. Discrete Appl. Math., 99, 71–90.Google Scholar

[116] Huck, A. 2001. On cycle-double covers of graphs of small oddness. Discrete Math., 229, 125–165.Google Scholar

[117] Huck, A., and Kochol, M. 1995. Five cycle double covers of some cubic graphs. J. Combin. Theory Ser. B, 64, 119–125.Google Scholar

[118] Isaacs, R. 1975. Infinite families of non-trivial trivalent graphs which are not Tait colorable. Amer. Math. Monthly, 82, 221–239.Google Scholar

[119] Itai, A., and Rodeh, M. 1978. Covering a graph by circuits. Pages 289–299 of: Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 62. Berlin: Springer-Verlag.

[120] Jackson, B. 1990. Shortest circuit covers and postman tours of graphs with a nowhere-zero 4-flow. SIAM J. Comput., 19, 659–665.Google Scholar

[121] Jackson, B. 1993. On circuit covers, circuit decompositions and Euler tours of graphs. Pages 191–210 of: Walker, K. (ed), Surveys in Combinatorics. London Math. Soc. Lecture Note Series, vol. 187. Cambridge: Cambridge University Press.

[122] Jackson, B. 1994. Shortest circuit covers of cubic graphs. J. Combin. Theory Ser. B, 60, 299–307.Google Scholar

[123] Jaeger, F. 1975. On nowhere-zero flows in multigraphs. Proceedings of the Fifth British Combinatorial Conference 1975. Congr. Numer., XV, 373–378.Google Scholar

[124] Jaeger, F. 1976. Balanced valuations and flows in multigraphs. Proc. Amer. Math. Soc., 55, 237–242.Google Scholar

[125] Jaeger, F. 1978a. On interval hypergraphs and nowhere-zero flow in graphs. Research Report of Mathematics Application and Information, Universite Scientifique et Medicale et Institut National Polytechnique de Grenoble, No. 126, Juillet.

[126] Jaeger, F. 1978b. Sue les flots dans les graphes et certaines valuations dans les hypergraphes d'intervalles. Pages 189–193 of: Benzaken, C. (ed), Proc. Colloque Alg`ebre Appliquèe et Combinatoire, Grenoble.

[127] Jaeger, F. 1979. Flows and generalized coloring theorems in graphs. J. Combin. Theory Ser. B, 26, 205–216.Google Scholar

[128] Jaeger, F. 1980. Tait's theorem for graphs with crossing number at most one. Ars Combin., 9, 283–287.Google Scholar

[129] Jaeger, F. 1984. On circular flows in graphs. Pages 391–402 of: Finite and Infinite Sets, Vol. I, II (Eger, 1981), Colloquia Mathematica Societatis János Bolyai 37. Amsterdam: North Holland.

[130] Jaeger, F. 1985. A survey of the cycle double cover conjecture. Pages 1–12 of: Alspach, B., and Godsil, C. (eds), Cycles in Graphs. Ann. Discrete Math., vol. 27. Amsterdam: North-Holland.

[131] Jaeger, F. 1988. Nowhere-zero flow problems. Pages 71–95 of: Beineke, L. W., and Wilson, R. J. (eds), Selected Topics in Graph Theory (3). London: Academic Press.

[132] Jaeger, F., and Swart, T. 1980. Conjecture 1. Pages 304–305 of: Deza, M., and Rosenberg, I.G. (eds), Combinatorics 79. Ann. Discrete Math., vol. 9. Amsterdam: North-Holland.

[133] Jamshy, U., and Tarsi, M. 1992. Shortest cycle covers and the cycle double cover conjecture. J. Combin. Theory Ser. B, 56, 197–204.Google Scholar

[134] Jamshy, U., Raspaud, A., and Tarsi, M. 1987. Short circuit covers for regular matroids with nowhere-zero, 5-flow. J. Combin. Theory Ser. B, 43, 354–357.Google Scholar

[135] Jensen, T. R. 2010. Splits of circuits. Discrete Math., 310, 3026.–3029.Google Scholar

[136] Jensen, T. R., and Toft, B. 1994. Graph Coloring Problems. John Wiley & Sons.

[137] Kahn, J., Robertson, N., and Seymour, P. D. 1987. Communication at Bellcore.

[138] Kaiser, T., and Raspaud, A. 2010. Perfect matchings with restricted intersection in cubic graphs. European J. Combin., 31, 1307.–1315.Google Scholar

[139] Kaiser, T., and Škrekovski, R. 2008. Cycles intersecting edges-cuts of prescribed sizes. SIAM J. Discrete Math., 22, 861–874.Google Scholar

[140] Kaiser, T., Kràl, D., Lidicky, B., and Nejedly, P. 2010. Short Cycle Covers of Graphs with Minimum Degree Three. SIAM J. Discrete Math., 24, 330–355.Google Scholar

[141] Kilpatrick, P. A. 1975. Tutte's first colour-cycle conjecture. Ph.D. thesis, Cape Town, South Africa.

[142] Knuth, D. E. 2008. The Art of Computer Programming. Vol. 4, Fascicle 0, Introduction to Combinatorial Algorithms and Boolean Function. Addison-Wesley.Google Scholar

[143] Kochol, M. 1993a. Construction of cyclically 6-edge-connected snarks. Technical Report TR-II-SAS-07/93-5, Institute for Information, Slovak Academy of Sciences, Bratislava, Slovakia.

[144] Kochol, M. 1993b. Cycle double covering of graphs. Technical Report TR-II-SAS-08/93-7, Institute for Informatics, Slovak Academy of Sciences, Bratislava, Slovakia.

[145] Kochol, M. 1996a. A cyclically 6-edge-connected snark of order 118. Discrete Math., 161, 297–300.Google Scholar

[146] Kochol, M. 1996b. Snarks without small cycles. J. Combin. Theory Ser. B, 67, 34–47.

[147] Kochol, M. 2000. Equivalence of Fleischner's and Thomassen's conjectures. J. Combin. Theory Ser. B, 78, 277–279.

[148] Kochol, M. 2001. Stable dominating circuits in snarks. Discrete Math., 233, 247–256.Google Scholar

[149] Kochol, M. 2004. Reduction of the 5-flow conjecture to cyclically 6-edgeconnected snarks. J. Combin. Theory Ser. B, 90, 139–145.

[150] Kochol, M. 2010. Smallest counterexample to the 5-flow conjecture has girth at least eleven. J. Combin. Theory Ser. B, 100, 381–389.

[151] Kostochka, A. V. 1995. The 7/5-conjecture strengthens itself. J. Graph Theory, 19, 65–67.

[152] Kotzig, A. 1958. Bemerkung zu den faktorenzerlegungen der endlichen paaren regulren graphen. Cnasopis Pěst. Mat., 83, 348–354.

[153] Kotzig, A. 1962. Construction of third-order Hamiltonian graphs. Časopis Pěst. Mat., 87, 148–168.

[154] Kotzig, A. 1964. Hamilton graphs and Hamilton circuits. Pages 63–82 of: Theory of Graphs and its Applications, Proceedings of the Symposium of Smolenice 1963. Prague: Publ. House Czechoslovak Acad. Sci.Google Scholar

[155] Kotzig, A., and Labelle, J. 1978. Strongly Hamiltonian graphs. Utilitas Mathematica, 14, 99–116.

[156] Kaàl, D., Nejedly, P., and Šámal, R. 2008. Short cycle covers of cubic graphs. KAM-DIMATIA Series 2008.(2008–846) Department of Applied Mathematics, Charles University, Prague, Czech.

[157] Kràl, D., Máčajová, E., Pangràc,, O., Raspaud, A., Sereni, J.-S., and Škoviera, M. 2009. Projective, affine, and abelian colourings of cubic graphs. European J. Combin., 30, 53–69.Google Scholar

[158] Kriesell, M. 2006. Contractions, cycle double covers, and cyclic colorings in locally connected graphs. J. Combin. Theory Ser. B, 96, 881–900.Google Scholar

[159] Kundu, S. 1974. Bounds on the number of disjoint spanning trees. J. Combin. Theory Ser. B, 17, 199–203.Google Scholar

[160] Kuratowski, C. 1930. Sur le problème des courbes gauches en topologie. Fund. Math., 15, 271–283.Google Scholar

[161] Lai, H.-J. 1994. Extension of a 3-coloring result of planar graphs. Unpublished manuscript.

[162] Lai, H.-J. 1995. The size of graphs without nowhere-zero 4-flows. J. Graph Theory, 19, 385–395.Google Scholar

[163] Lai, H.-J., and Lai, H.-Y. 1991a. Cycle covering of plane triangulations. J. Combin. Math. Combin. Comput., 10, 3–21.Google Scholar

[164] Lai, H.-J., and Lai, H.-Y. 1991b. Small cycle covers of planar graphs. Congr. Numer., 85, 203–209.

[165] Lai, H.-J., and Zhang, C.-Q. 2001. Hamilton weight and Petersen minor. J. Graph Theory, 38, 197–219.Google Scholar

[166] Lai, H.-J., Yu, X.-X., and Zhang, C.-Q. 1994. Small circuit double covering of cubic graphs. J. Combin. Theory Ser. B, 60, 177–194.Google Scholar

[167] Little, C. H. C., and Ringeisen, R. D. 1978. On the strong graph embedding conjecture. Pages 479–487 of: Proceeding of the 9th Southeastern Conference on Combinatorics, Graph Theory and Computing, Utilitas Mathematica.Google Scholar

[168] Little, C. H. C., Tutte, W. T., and Younger, D. H. 1988. A theorem on integer flows. Ars Combin., 26A, 109–112.Google Scholar

[169] Loupekine, F., and Watkins, J. J. 1985. Cubic graphs and the fourcolor theorem. Pages 519–530 of: Alavi, Y., Chartrand, G., Lesniak, L., Lick, D.R., and Wall, C.E. (eds), Graph Theory and its Application to Algorithms and Computer Science. New York: John Wiley & Sons, Inc.

[170] Lovász, L. 1978. Kneser's conjecture chromatic number, and homotopy. J. Combin. Theory Ser. A, 25, 319–324.Google Scholar

[171] MacGillivray, G., and Seyffarth, K. 2001. Classes of line graphs with small cycle double covers. Austral. J. Combin., 24, 91–114.Google Scholar

[172] Markström, K. 2011. Even cycle decompositions of 4-regular graphs and line graphs. Discrete Math., doi:10.1016.j.disc.2011.12.007.Google Scholar

[173] Massey, W. S. 1967. Algebraic Topology: An Introduction. New York: Springer-Verlag.

[174] Matthews, K. R. 1978. On the eulericity of a graph. J. Graph Theory, 2, 143–148.Google Scholar

[175] Máčajová, E., and Škoviera, M. 2005. Fano colourings of cubic graphs and the Fulkerson conjecture. Theor. Comput. Sci., 349, 112–120.Google Scholar

[176] Máčajová, E., and Škoviera, M. 2009. On a Conjecture of Fan and Raspaud. Electronic Notes in Discrete Mathematics, 34, 237–241.Google Scholar

[177] Máčajová, E., Raspaud, A., and Škoviera, M. 2005. Abelian colourings of cubic graphs. Electronic Notes in Discrete Mathematics, 22, 333–339.Google Scholar

[178] Máčajová, E., Raspaud, A., Tarsi, M., and Zhu, X.-D. 2011. Short cycle covers of graphs and nowhere-zero flows. J. Graph Theory, 68, 340–348.Google Scholar

[179] McGuinness, S. 1984. The double cover conjecture. Ph.D. thesis, Queen's University, Kingston, Ontario, Canada.

[180] Menger, K. 1927. Zur allgemeinen Kurventheorie. Fund. Math., 10, 96–115.Google Scholar

[181] Mohar, B. 2010. Strong embeddings of minimum genus. Discrete Math., 310, 2595–2599.Google Scholar

[182] Mohar, B., and Thomassen, C. 2001. Graphs on Surfaces. Baltimore, MD: The Johns Hopkins University Press.

[183] Naserasr, R., and Škrekovski, R. 2003. The Petersen graph is not 3-edge-colorable – a new proof. Discrete Math., 268, 325–326.Google Scholar

[184] Nash-Williams, C.St., J. A. 1961. Edge-disjoint spanning trees of finite graphs. J. London Math. Soc., s1–36, 445–450.Google Scholar

[185] Nelson, D., Plummer, M. D., Robertson, N., and Zha, X.-Y. 2011. On a conjecture concerning the Petersen graph. Electronic Journal of Combinatorics, 18, P20.Google Scholar

[186] Nowakowski, R. J., and Seyffarth, K. 2008. Small cycle double covers of products I: Lexicographic product with paths and cycles. J. Graph Theory, 57, 99–123.Google Scholar

[187] Nowakowski, R. J., and Seyffarth, K. 2009. Small cycle double covers of products II: Categorical and strong products with paths and cycles. Graph and Combinatorics, 25, 385–400.Google Scholar

[188] Ore, O. 1967. The Four-Color Problem. New York: Academic Press.

[189] Petersen, J. 1891. Die Theorie der Regulären Graphen. Acta Math., 15, 193–220.Google Scholar

[190] Petersen, J. 1898. FSur le théoreme de Tait. Intermed. Math., 15, 225–227.Google Scholar

[191] Polesskii, V. P. 1971. A lower bound for the reliability of information network. Probl. Peredachi Inf., 7:2, 88–96.Google Scholar

[192] Preissmann, M. 1981. Sur les colorations des arêtes des graphes cubiques, Thèse de Doctorat de 3eme. Ph.D. thesis, Université de Grenoble, France.

[193] Preissmann, M. 1982. Snarks of order 18. Discrete Math., 42, 125–126.Google Scholar

[194] Rizzi, R. 2001. On 4-connected graphs without even cycle decompositions. Discrete Math., 234, 181–186.Google Scholar

[195] Robertson, N., Seymour, P.D., and Thomas, R.Cyclically 5-connected cubic graphs. in preparation.

[196] Robertson, N., Seymour, P.D., and Thomas, R.Excluded minors in cubic graphs. in preparation.

[197] Robertson, N., Sanders, D., Seymour, P. D., and Thomas, R. 1997a. The 4-color theorem. J. Combin. Theory Ser. B, 70, 2–44.Google Scholar

[198] Robertson, N., Seymour, P. D., and Thomas, R. 1997b. The Tutte's 3-edge-coloring conjecture. J. Combin. Theory Ser. B, 70, 166–183.Google Scholar

[199] Sanders, D. P., and Thomas, R.Edge 3-coloring cubic apex graphs. in preparation.

[200] Sanders, D. P., Seymour, P.D., and Thomas, R.Edge 3-coloring cubic doublecross graphs. in preparation.

[201] Seyffarth, K. 1989. Cycle and Path Covers of Graphs. Ph.D. thesis, University of Waterloo, Ontario, Canada.

[202] Seyffarth, K. 1992. Hajós' conjecture and small cycle double covers of planar graphs. Discrete Math., 101, 291–306.Google Scholar

[203] Seyffarth, K. 1993. Small cycle double covers of 4-connected planer. Combinatorica, 13, 477–482.Google Scholar

[204] Seymour, P. D. 1979a. On multi-colorings of cubic graphs and the conjecture of Fulkerson and Tutte. Proc. London Math. Soc., s3–38, 423–460.Google Scholar

[205] Seymour, P. D. 1979b. Sums of circuits. Pages 342–355 of: Bondy, J. A., and Murty, U.S.R. (eds), Graph Theory and Related Topics. New York: Academic Press.

[206] Seymour, P. D. 1981a. Even circuits in planar graphs. J. Combin. Theory Ser. B, 31, 327–338.Google Scholar

[207] Seymour, P. D. 1981b. Nowhere-zero 6-flows. J. Combin. Theory Ser. B, 30, 130–135.Google Scholar

[208] Seymour, P. D. 1981c. On Tutte's extension of the four-color problem. J. Combin. Theory Ser. B, 31, 82–94.Google Scholar

[209] Seymour, P. D. 1990. Communication at Cycle Double Cover Conjecture Workshop, Barbados, February 25–March 4.

[210] Seymour, P. D. 1995. Personal communication.

[211] Seymour, P. D. 2012. Personal communication.

[212] Seymour, P. D., and Truemper, K. 1998. A Petersen on a Pentagon. J. Combin. Theory Ser. B, 72, 63–79.Google Scholar

[213] Shu, J., and Zhang, C.-Q. 2005. A note about shortest cycle covers. Discrete Math., 301, 232–238.Google Scholar

[214] Shu, J., Zhang, C.-Q., and Zhang, T.-Y. 2012. Flows and parity subgraphs of graphs with large odd edge connectivity. J. Combin. Theory Ser. B, (to appear).Google Scholar

[215] Stahl, S. 1998. The multichromatic numbers of some Kneser graphs. Discrete Math., 185, 287–291.Google Scholar

[216] Steinberg, R. 1976. Grötzsch's Theorem dualized. M.Phil. thesis, University of Waterloo, Ontario, Canada.

[217] Steinberg, R. 1984. Tutte's 5-flow conjecture for projective plane. J. Graph Theory, 8, 277–285.Google Scholar

[218] Stephens, D. C., Tucker, T. W., and Zha, X.-Y. 2007. Representativity of Cayley maps. Preprint.

[219] Szekeres, G. 1973. Polyhedral decompositions of cubic graphs. Bull. Austral. Math. Soc., 8, 367–387.Google Scholar

[220] Tait, P. G. 1880. Remarks of the coloring of maps. Proc. R. Soc. Edinburgh, 10, 729.Google Scholar

[221] Tarsi, M. 1986. Semi-duality and the cycle double cover conjecture. J. Combin. Theory Ser. B, 41, 332–340.Google Scholar

[222] Tarsi, M. 2010. Personal communication.

[223] Thomas, R.Generalizations of The Four Color Theorem. http://people.math.gatech.edu/∼thomas/FC/generalize.html.

[224] Thomas, R. 1998. An update on the four-color theorem. Notices of the AMS, 45, 848–859.Google Scholar

[225] Thomason, A. 1978. Hamiltonian Cycles and uniquely edge colorable graphs. Ann. Discrete Math., 3, 259–268.Google Scholar

[226] Thomason, A. 1982. Cubic graphs with three hamiltonian cycles are not always uniquely edge colorable. J. Graph Theory, 6, 219–221.Google Scholar

[227] Thomassen, C. 1997. On the complexity of finding a minimum cycle covers of graphs. SIAM J. Comput., 26, 675–677.Google Scholar

[228] Tutte, W. T. 1946. On Hamilton circuits. J. London Math. Soc., s1–21, 98–101.Google Scholar

[229] Tutte, W. T. 1949. On the imbedding of linear graphs in surfaces. Proc. London Math. Soc., s2–51, 474–483.Google Scholar

[230] Tutte, W. T. 1954. A contribution on the theory of chromatic polynomial. Canad. J. Math., 6, 80–91.Google Scholar

[231] Tutte, W. T. 1956. A class of Abelian groups. Canad. J. Math., 8, 13–28.Google Scholar

[232] Tutte, W. T. 1961. On the problem of decompositing a graph into n connected factors. J. London Math. Soc., s1–36, 221–230.Google Scholar

[233] Tutte, W. T. 1966. On the algebraic theory of graph colourings. J. Combin. Theory, 1, 15–50.Google Scholar

[234] Tutte, W. T. 1967. A geometrical version of the four color problem. In: Bose, R. C., and Dowling, T. A. (eds), Combinatorial Mathematics and its Applications. Chapel Hill, NC: University of North Carolina Press.

[235] Tutte, W. T. 1976. Hamiltonian circuits. Pages 193–199 of: Colloquio Internazional sulle Teorie Combinatorics, Atti dei Convegni Lincei 17, Accad. Naz. Lincei, Roma I.

[236] Tutte, W. T. 1984. Graph Theory. Encyclopedia of Mathematics and Its Applications, vol. 21. Cambridge Mathematical Library.

[237] Tutte, W. T. 1987. Personal correspondence with H. Fleischner (July 22, 1987).

[238] Veblen, O. 1912–1913. An application of modular equations in analysis situs. Ann. Math., 12, 86–94.Google Scholar

[239] Vince, A. 1988. Star chromatic number. J. Graph Theory, 12, 551–559.Google Scholar

[240] Watkins, J. J. 1989. Snarks. In: Capobianco, M., Guan, M., Hsu, D. F., and Tian, F. (eds), Graph Theory and Its Applications: East and West, Proceeding of the First China–USA International Graph Theory Conference. New York: New York Academy of Sciences.

[241] Watkins, J. J., and Wilson, R. J. 1991. A survey of snarks. Pages 1129–1144 of: Alavi, Y., Chartrand, G., Oellermann, O.R., and Schwenk, A.J. (eds), Graph Theory, Combinatorics, and Applications, Proceeding of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs. New York: John Wiley & Sons, Inc.Google Scholar

[242] West, D. B. 1996. Introduction to Graph Theory. Upper Saddle River, NJ: Prentice Hall.

[243] White, A. T. 1984. Graphs, Groups and Surfaces. Revised edn. North-Holland Mathematics Studies, vol. 8. Amsterdam: North-Holland.

[244] Wilson, R. J. 1976. Problem 2. In: Proc. 5th British Comb. Conf., Utilitas Mathematica.

[245] Xie, D.-Z., and Zhang, C.-Q. 2009. Flows, flow-pair covers, cycle double covers. Discrete Math., 309, 4682–4689.Google Scholar

[246] Xu, R. 2009. Note on cycle double covers of graphs. Discrete Math., 309, 1041–1042.Google Scholar

[247] Ye, D. 2010. Personal communication.

[248] Ye, D., and Zhang, C.-Q. 2009. Circumference and Circuit Double Covers. Preprint.

[249] Ye, D., and Zhang, C.-Q. 2012. Cycle Double Covers and Semi-Kotzig Frame. European J. Combin., 33, 624–631.Google Scholar

[250] Younger, D. H. 1983. Integer flows. J. Graph Theory, 7, 349–357.Google Scholar

[251] Zha, X.-Y. 1995. The closed 2-cell embeddings of 2-connected doubly toroidal graphs. Discrete Math., 145, 259–271.Google Scholar

[252] Zha, X.-Y. 1996. Closed 2-cell embeddings of 4 cross-cap embeddable graphs. Discrete Math., 162, 251–266.Google Scholar

[253] Zha, X.-Y. 1997. Closed 2-cell embeddings of 5-crosscap embeddable graphs. European J. Combin., 18, 461–477.Google Scholar

[254] Zhang, C.-Q. 1990. Minimum cycle coverings and integer flows. J. Graph Theory, 14, 537–546.Google Scholar

[255] Zhang, C.-Q. 1994. On even circuit decompositions of eulerian graphs. J. Graph Theory, 18, 51–57.Google Scholar

[256] Zhang, C.-Q. 1995. Hamiltonian weights and unique 3-edge-colorings of cubic graphs. J. Graph Theory, 20, 91–99.Google Scholar

[257] Zhang, C.-Q. 1996a. Nowhere-zero 4-flows and cycle double covers. Discrete Math., 154, 245–253.Google Scholar

[258] Zhang, C.-Q. 1996b. On embeddings of graphs containing no K5-minor. J. Graph Theory, 21, 401–404.Google Scholar

[259] Zhang, C.-Q. 1997. Integer Flows and Cycle Covers of Graphs. New York: Marcel Dekker.

[260] Zhang, C.-Q. 2002. Circular flows of nearly eulerian graphs and vertexsplitting. J. Graph Theory, 40, 147–161.Google Scholar

[261] Zhang, C.-Q. 2010. Cycle covers (I) – minimal contra pairs and Hamilton weights. J. Combin. Theory Ser. B, 100, 419–438.Google Scholar

[262] Zhang, X.-D., and Zhang, C.-Q. 2012. Kotzig frames and circuit double covers. Discrete Math., 312, 174–180.Google Scholar

[263] Zhu, X.-D. 2001. Circular chromatic number: a survey. Discrete Math., 229, 371–410.Google Scholar

[264] Zhu, X.-D. 2006. Recent developments in circular colouring of graphs. Pages 497–550 of: Klazar, M., Kratochvil, J., Matousek, J., Thomas, R., and Valtr, P. (eds), Topics in Discrete Mathematics. Springer.