Oriented Berge-Fulkerson conjecture v0.1

Here’s the solution for Petersen graph:

Снимок экрана 2018-12-06 в 3.46.52

Oriented 6-cycle 4-cover for Petersen graph (matching is shown in dotted edges) (image is created in Geogebra)

Up to isomorphisms, there’s only 1 solution for Petersen graph.

There are 2 types of vertices:

  • blue — (we’ll call them oriented) — each pair of edges, that goes through this vertex in every cycle, is oriented in the same direction
  • black — (we’ll call them non-oriented)  — same pairs are oriented differently in different cycles

Here’s the solution for one of Blanuša snarks (todo: probably it’s the first Blanuša snark)

Снимок экрана 2018-12-07 в 22.40.05

  • Black and violet edges are rich. Every edge is covered 4 times, and now we take a look at the neighboring edges. If we have 4 different possibilities, then the edge is rich.
  • Red and orange edges are poor — there are only 2 possibilities which occur twice in the covering.

Black and red edges constitute 2-factors, violet and orange edges constitute perfect matchings.

Oriented vs non-oriented — the story is about o6c4c (oriented 6-cycle 4-cover). Rich vs poor — the story is about general 6c4c.

This classification of edges is connected to Petersen coloring: if the 6c4c solution comes from Petersen coloring, we’ll get the ordinary definition of rich (all 5 colors in the neighborhood) and poor edges (only 3 colors).

Computational verification shows, that every (cyclically 4-edge connected with girth at least 5) snark with up to (and including) 30 vertices has at least 1 oriented Berge-Fulkerson solution. We’ll state this as a conjecture (oriented Berge-Fulkerson conjecture): every bridgeless cubic graph has an oriented 6-cycle 4-cover (these cycles are called 2-factors, because they are incident to every vertex in the graph) (the complement to these cycles are perfect matchings).

So this construction is also a clarification (and errata) to the 2 pages at Open Problems Garden:

Some notation

  • s0 — number of circuits (circuit is a connected cycle; there are 12 in the solution for Petersen graph)
  • s1 — number of rich edges (15 for Petersen graph)
  • s2 — half of the number of perfect matchings with even number of rich edges (so in general it’s equal to 0, 1, 2 or 3) (0 for Petersen graph)
  • or — number of oriented vertices
  • t1 — number of poor edges which connect oriented with oriented vertex
  • (t2 — number of poor edges which connect oriented with non-oriented vertex) (not used)
  • t3 — number of rich edges which connect oriented with non-oriented vertex
  • t4 — number of rich edges which connect non-oriented with non-oriented vertex
  • total_poor_comps — number of connected components of poor edges
  • odd_poor_comps_2-factors — number of 2-factors with odd number of connected components of poor edges (so it can be one of 0, 1, 2, 3, 4, 5 or 6) (likewise we can define things as, e. g., odd_rich_comps_2-factors, where we count 2-factors with odd number of connected components of rich edges; or odd_poor_comps_matchings, where we count perfect matchings with odd number of connected components of poor edges)
  • odd_poor_2-factors — number of 2-factors with odd number of poor edges (so it can be one of 0, 1, 2, 3, 4, 5 or 6) (so we don’t count connected components of edges, just edges themselves) (so, s2 is same as even_rich_matchings / 2)
  • nz-mod-k — nowhere-zero mod-k flow solution (which maybe doesn’t exist), built with 2-factors having weights from 0 to k — 1 and using modular arithmetics (we are interested in k = 5 and k = 6)

General case

These statements are easy to prove:

  • or has same parity as t3
  • or has same parity in all possible orientations of fixed 6c4c solution

Some not yet proven computational observations (checked on snarks with small number of vertices, I will later specify these numbers and decipher every notation):

  • There’s always at least one dominating circuit which goes through all oriented vertices
  • If or = 0, then s2 = 3
  • If or = 0, then s0 has same parity as s1
  • There are no solutions with or = 1
  • There are no solutions with 16 rich edges
  • There are never less than 15 rich edges for snarks
  • if t1 + t3 < 9, then s0 + s1 + s2 is odd
  • There are no solutions with t1 + t3 = 7
  • odd_poor_comps_2-factors is even, odd_rich_comps_2-factors is even, odd_poor_comps_matching is even (but odd_rich_comps_matching may have any parity) (if we count not components but just the edges then this becomes obvious)
  • if we have o6c4c, nz-mod5 and don’t have nz-mod6, then or > 2 and s0 is even
  • if total_poor_comps = 1, then s1 + s2 is odd;

sometimes patterns start to break only when number of vertices is huge (usually works upto 26 and breaks on 28 vertices):

  • upto 26: if total_poor_comps = 1, and if the solution is orientable (so we have o6c4c) then s0 is even; breaks on 28.05g611

Case of splitting into 2 separate 6cdcs

If the 6c4c solution comes from Petersen coloring, then its also possible to divide the circuits into 2 separate 6-cycle double covers (we’ll denote this as 2x6cdcs). If we have a general 6c4c solution, then in case we have such decomposition:

  • it’s easy to show that we can have only 1 such decomposition up to circuit isomorphisms

Also we have some unproven statements for this case:

  • total_poor_comps > 1
  • odd_poor_2-factors = 0
  • s2 is either 0 or 3
  • if the solution is orientable (so we have o6c4c) then
    • s0 is even
    • or + s1 is even (or same as saying that t4 is even)


Q: Are there any other graphs with 0 poor edges?

A: Yes, later I’ll show here an example


Q: Are there graphs with or = 0 and with splitting into 2x6cdcs?


My research on cycle double cover conjecture

Hi! Announcement here!

My name is Nikolay Ulyanov and here I will gradually publish till the end of 2018 all of my findings surrounding:

  • cycle double cover conjecture, from 2016 to 2018;
  • graceful labeling conjecture, from 2012 to 2016;
  • Graham-Häggkvist conjecture, from 2014 to 2017.