Máčajová–Škoviera odd-cut conjecture for bridgeless cubic graphs

About 8 years old · traced to

Let GG be a bridgeless cubic graph. A perfect matching is a set of edges meeting every vertex exactly once, and an edge-cut is the set of edges joining a vertex subset to its complement. Máčajová–Škoviera conjecture. Every bridgeless cubic graph has two perfect matchings such that their intersection does not contain an edge-cut of odd cardinality. This is one of the weaker statements implied by the Berge–Fulkerson conjecture and is stated in the source as having been proved by Kardoš, Máčajová and Zerafa.

References

Primary source

Jan Goedgebeur, Davide Mattiolo, Giuseppe Mazzuoccolo, Jarne Renders, Luca Toffanetti and Isaak H. Wolf, “On the existence of factors intersecting sets of cycles in regular graphs”, arXiv:2411.09806 (2026).

Additional references

2 papers in this index state this conjecture (2018–2024). The statement above is taken from the most recent of them; the others are arXiv:1811.08363.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.