Construction, Study and Applications of Snarks

The Cycle Double Cover Conjecture (CDCC) and the Nowhere-Zero 5-Flow Conjecture (NZ5FC) are two of the most outstanding conjectures in graph theory. Surprisingly, the investigation of a colouring theorem, namely, the Cycle Plus Triangles Theorem (CPT-Theorem), originally conjectured by P.Erdos, leads to a conjecture which opens up a new approach to tackling both the CDCC and NZ5FC. This new conjecture is called Bipartizing Matching Conjecture (BMC) and its truth in combination with the Dominating Cycle Conjecture would solve both the CDCC and NZ5FC. This project investigates first, under which additional assumptions the validity of the NZ5FC and of the CDCC implies that cubic graphs with dominating cycle admit disjoint BMs. In all the conjectures above, however, snarks are the graphs to deal with. Therefore the main content of the project will be the study of snarks and the verification of the above conjecture for well known but also new classes of snarks. Moreover this project aims at estimating the independence number of 4-regular graphs which are somewhat more general than CPT-graphs.

The Cycle Double Cover Conjecture (CDCC) and the Nowhere-Zero 5-Flow Conjecture (NZ5FC) are two of the most outstanding conjectures in graph theory. Surprisingly, the investigation of a colouring theorem, namely, the Cycle Plus Triangles Theorem (CPT-Theorem), originally conjectured by P.Erdos, leads to a conjecture which opens up a new approach to tackling both the CDCC and NZ5FC. This new conjecture is called Bipartizing Matching Conjecture (BMC) and its truth in combination with the Dominating Cycle Conjecture would solve both the CDCC and NZ5FC. This project investigates first, under which additional assumptions the validity of the NZ5FC and of the CDCC implies that cubic graphs with dominating cycle admit disjoint BMs. In all the conjectures above, however, snarks are the graphs to deal with. Therefore the main content of the project will be the study of snarks and the verification of the above conjecture for well known but also new classes of snarks. Moreover this project aims at estimating the independence number of 4-regular graphs which are somewhat more general than CPT-graphs.