Circuit double cover of graphs
The Circuit (Cycle) Double Cover Conjecture (CDC conjecture) states that every \(2\)-connected graph has a family \(\mathcal{F}\) of circuits such that every edge of the graph is covered by (contained in) precisely two members of \(\mathcal{F}\). (A circuit in this book is a connected \(2\)-regular graph.) This conjecture is one of the major open problems in graph theory. One reason for this is its close relationship with topological graph theory, integer flow theory, graph coloring and the structure of snarks.NEWLINENEWLINEThis book provides a thorough exploration of the general conjecture, the approaches that have been developed, and connections with different subareas. The author zooms in to focus on the rich body of results, methods and questions, directly and indirectly related to the CDC conjecture. The book is presented in a well-written form.NEWLINENEWLINEIn order to keep the main theme of the book as focused as possible, the author decided to concentrate for the most part on results and techniques in structural graph theory. Topological results are presented only if either they can be obtained by combinatorial methods or they are needed as background for a combinatorial approach.NEWLINENEWLINEWithout using flow theory, \(3\)-edge-coloring of cubic graphs becomes one of the major techniques in this book. Since flow theory does provide some powerful tools, it will be covered in later chapters.NEWLINENEWLINEMost of the basic lemmas and theorems of integer flow theory in this book are presented in an appendix. Moreover, a set of appendices collects some fundamental graph theoretical results which are useful in the study of circuit covers. The appendix also contains hints to the exercises and a glossary with basic and some special terminology.
- Circle graphs and the cycle double cover conjecture
- On covers of graphs
- Cycle double covers via kotzig graphs
- A note on shortest sign-circuit cover of signed 3-edge-colorable cubic graphs
- On even cycle decompositions of line graphs of cubic graphs
- Signed circuit cover of bridgeless signed graphs
- Rotation snark, Berge-Fulkerson conjecture and Catlin's 4-flow reduction
- Cycle double covers and non-separating cycles
- Cycle double covers containing certain circuits in cubic graphs having special structures
- Nowhere-zero flows on signed regular graphs
- Perfect matching covering, the Berge-Fulkerson conjecture, and the Fan-Raspaud conjecture
- Hamiltonian cycles and 1-factors in 5-regular graphs
- Cycle double covers in cubic graphs having special structures
- Strong circuit double cover of some cubic graphs
- Oriented circuit double cover and circular flow and colouring
- Cyclic 4-colorings of graphs on surfaces
- Orientable one-circuit double covers
- Construction of permutation snarks
- scientific article; zbMATH DE number 3937197 (Why is no real title available?)
- Circuit extension and circuit double cover of graphs
- scientific article; zbMATH DE number 978847 (Why is no real title available?)
- scientific article; zbMATH DE number 6965186 (Why is no real title available?)
- Vertices with the second neighborhood property in Eulerian digraphs
- Minimum \(T\)-joins and signed-circuit covering
- Cubic graphs with no short cycle covers
- Extension to 3-colorable triangulations
- Circuit double covers of graphs
- 5-Cycle Double Covers, 4-Flows, and Catlin Reduction
- Homomorphisms of Cayley graphs and cycle double covers
- Kotzig frames and circuit double covers
- Five-cycle double cover and shortest cycle cover
- Counting circuit double covers
- Signed cycle double covers
- Cycle separating cuts in possible counterexamples to the cycle double cover and the Berge-Fulkerson conjectures
- Non-separating cycles and 5-cycle double covers
- Approximate cycle double cover
- An infinite family of snarks with perfect matching cover index 4
- A note on Alon-Tarsi shortest cycle cover conjecture
- Treelike snarks
This page was built for publication: Circuit double cover of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2884704)
