UID:
almafu_9959245762002883
Umfang:
1 online resource (xxi, 357 pages) :
,
digital, PDF file(s).
Ausgabe:
1st ed.
ISBN:
1-107-22396-2
,
0-511-86315-2
,
1-280-64724-8
,
9786613633293
,
1-139-37787-6
,
1-139-37501-6
,
1-139-37644-6
,
1-139-37930-5
,
1-139-37102-9
Serie:
London Mathematical Society lecture note series ; 399
Inhalt:
The famous Circuit Double Cover conjecture (and its numerous variants) is considered one of the major open problems in graph theory owing to its close relationship with topological graph theory, integer flow theory, graph coloring and the structure of snarks. It is easy to state: every 2-connected graph has a family of circuits covering every edge precisely twice. C.-Q. Zhang provides an up-to-date overview of the subject containing all of the techniques, methods and results developed to help solve the conjecture since the first publication of the subject in the 1940s. It is a useful survey for researchers already working on the problem and a fitting introduction for those just entering the field. The end-of-chapter exercises have been designed to challenge readers at every level and hints are provided in an appendix.
Anmerkung:
Title from publisher's bibliographic system (viewed on 05 Oct 2015).
,
Cover; Series; Title; Copyright; Dedication; Contents; Foreword; Foreword; Preface; 1: Circuit double cover; 1.1 Circuit double cover conjecture; 1.2 Minimal counterexamples; 1.3 3-edge-coloring and even subgraph cover; 1.4 Circuit double covers and graph embeddings; 1.5 Open problems; 1.6 Exercises; 2: Faithful circuit cover; 2.1 Faithful circuit cover; 2.2 3-edge-coloring and faithful cover; Applications of Lemma 2.2.1; 2.3 Construction of contra pairs; Isaacs-Fleischner-Jackson product; 2.4 Open problems; 2.5 Exercises; Admissible eulerian weights; Faithful cover; Contra pairs
,
3: Circuit chain and Petersen minor3.1 Weight decomposition and removable circuit; 3.2 Cubic minimal contra pair; 3.3 Minimal contra pair; 3.4 Structure of circuit chain; 3.5 Open problems; 3.6 Exercises; Structure of circuit chain; Girth for faithful cover; Miscellanies; 4: Small oddness; 4.1 k-even subgraph double covers; 4.2 Small oddness; 4.3 Open problems; 4.4 Exercises; 5: Spanning minor, Kotzig frames; 5.1 Spanning Kotzig subgraphs; Generalizations of Kotzig graphs; Various spanning minors; 5.2 Kotzig frames; Proof of Theorem 5.2.6; 5.3 Construction of Kotzig graphs
,
5.4 Three-Hamilton circuit double coversStrong Kotzig graphs; Uniquely 3-edge-colorable graphs; Hamilton weighted graphs; 5.5 Open problems; From frames to CDC; Existence of Kotzig frames; 5.6 Exercises; Constructions; Examples, counterexamples; Spanning minors; 6: Strong circuit double cover; 6.1 Circuit extension and strong CDC; 6.2 Thomason's lollipop method; Almost Hamilton circuit; 6.3 Stable circuits; 6.4 Extension-inheritable properties; 6.5 Extendable circuits; 6.6 Semi-extension of circuits; Further generalizations; 6.7 Circumferences; 6.8 Open problems; 6.9 Exercises
,
7: Spanning trees, supereulerian graphs7.1 Jaeger Theorem: 2-even subgraph covers; Supereulerian graphs, even subgraph covers; Spanning trees, supereulerian graphs; 4-edge-connected graphs; 7.2 Jaeger Theorem: 3-even subgraph covers; Smallest counterexample to the theorem; The first proof of Theorem 7.2.1; The second proof of Theorem 7.2.1; 7.3 Even subgraph 2k-covers; 4-covers; 6-covers; Berge-Fulkerson conjecture; 7.4 Catlin's collapsible graphs; Examples of collapsible graphs; Maximal collapsible subgraph and graph reduction; Contractible configurations; 7.5 Exercises
,
3-even subgraph coversBerge-Fulkerson conjecture; Collapsible graphs; 8: Flows and circuit covers; 8.1 Jaeger Theorems: 4-flow and 8-flow; 8.2 4-flows; Even subgraph covers; Parity subgraph decompositions; Evenly spanning even subgraphs; Faithful cover; 8.3 Seymour Theorem: 6-flow; Even subgraph 6-covers; 8.4 Contractible configurations for 4-flow; 8.5 Bipartizing matching, flow covering; 8.6 Exercises; 4-flows; Faithful covers; Seymour's operation; Miscellanies; 9: Girth, embedding, small cover; 9.1 Girth; 9.2 Small genus embedding; 9.3 Small circuit double covers; 9.4 Exercises
,
Embedded graphs
,
English
Weitere Ausg.:
ISBN 1-107-26359-X
Weitere Ausg.:
ISBN 0-521-28235-7
Sprache:
Englisch
Fachgebiete:
Mathematik
URL:
https://doi.org/10.1017/CBO9780511863158
