Oriented Berge-Fulkerson conjecture v0.1

Here’s the solution for Petersen graph:

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 the first Blanuša snark

• 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:

• http://www.openproblemgarden.org/op/m_n_cycle_covers (The orientable eight cycle four cover conjecture)
• http://www.openproblemgarden.org/op/cycle_double_cover_conjecture (The oriented cycle four cover conjecture)

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 non-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&A

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?

A: TODO

…