O'Reilly logo

Circuit Double Cover of Graphs by Cun-Quan Zhang

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Appendix BSnarks, Petersen graph

Methods developed for 3-edge-colorings of cubic graphs play a central role in the study of circuit cover problems. In this chapter, we present some elementary and commonly used results, and methods in this subject.

B.1 3-edge-coloring of cubic graphs, snarks

The subject of 3-edge-colorings of cubic graphs has been extensively studied in graph theory because of its close relation with the map 4-coloring problem.

Theorem B.1.1 (Tait [220]) Every bridgeless planar graph is 4-face colorable if and only if every bridgeless, cubic, planar graph is 3-edge-colorable.

Proof See Theorem 9.12 of [18], or Theorem 11.4 of [19].     

Theorem B.1.2 (The 4-Color Theorem, Appel and Haken [5], [7], [6] and [197], [224]) Every bridgeless ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required