Cores, Joins and the Fano-Flow Conjectures

• Autorzy: Ligang Jin , Eckhard Steffen , Giuseppe Mazzuoccolo
• Języki publikacji: EN

Abstrakty

EN

The Fan-Raspaud Conjecture states that every bridgeless cubic graph has three 1-factors with empty intersection. A weaker one than this conjecture is that every bridgeless cubic graph has two 1-factors and one join with empty intersection. Both of these two conjectures can be related to conjectures on Fano-flows. In this paper, we show that these two conjectures are equivalent to some statements on cores and weak cores of a bridgeless cubic graph. In particular, we prove that the Fan-Raspaud Conjecture is equivalent to a conjecture proposed in [E. Steffen, 1-factor and cycle covers of cubic graphs, J. Graph Theory 78 (2015) 195–206]. Furthermore, we disprove a conjecture proposed in [G. Mazzuoccolo, New conjectures on perfect matchings in cubic graphs, Electron. Notes Discrete Math. 40 (2013) 235–238] and we propose a new version of it under a stronger connectivity assumption. The weak oddness of a cubic graph G is the minimum number of odd components (i.e., with an odd number of vertices) in the complement of a join of G. We obtain an upper bound of weak oddness in terms of weak cores, and thus an upper bound of oddness in terms of cores as a by-product.

Słowa kluczowe

EN

cubic graphs; Fan-Raspaud Conjecture; cores; weak-cores

Kategorie tematyczne

• 05C70: Factorization, matching, partitioning, covering and packing

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 38
• Numer: 1
• Strony: 165-175

Daty

wydano

2018-02-01

otrzymano

2016-01-20

poprawiono

2016-10-24

zaakceptowano

2016-10-26

online

2017-12-30

Twórcy

autor

Ligang Jin

• , , Warburger Str. 100, ,

autor

Eckhard Steffen

• , , Warburger Str. 100, ,

autor

Giuseppe Mazzuoccolo

• , , Strada Le Grazie 15, ,

Identyfikatory

DOI

10.7151/dmgt.1999