Geodesic
Cores, Joins and the Fano-Flow Conjectures
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 1, pp. 165-175.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: cubic graphs, Fan-Raspaud Conjecture, cores, weak-cores 
@article{DMGT_2018_38_1_a13,
     author = {Jin, Ligang and Steffen, Eckhard and Mazzuoccolo, Giuseppe},
     title = {Cores, {Joins} and the {Fano-Flow} {Conjectures}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {165--175},
     publisher = {mathdoc},
     volume = {38},
     number = {1},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a13/}
}
TY  - JOUR
AU  - Jin, Ligang
AU  - Steffen, Eckhard
AU  - Mazzuoccolo, Giuseppe
TI  - Cores, Joins and the Fano-Flow Conjectures
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 165
EP  - 175
VL  - 38
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a13/
LA  - en
ID  - DMGT_2018_38_1_a13
ER  - 
%0 Journal Article
%A Jin, Ligang
%A Steffen, Eckhard
%A Mazzuoccolo, Giuseppe
%T Cores, Joins and the Fano-Flow Conjectures
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 165-175
%V 38
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a13/
%G en
%F DMGT_2018_38_1_a13
Jin, Ligang; Steffen, Eckhard; Mazzuoccolo, Giuseppe. Cores, Joins and the Fano-Flow Conjectures. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 1, pp. 165-175. http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a13/

[1] G.H. Fan and A. Raspaud, Fulkerson’s conjecture and circuit covers, J. Combin. Theory Ser. B 61 (1994) 133–138. doi:10.1006/jctb.1994.1039

[2] D.R. Fulkerson, Blocking and anti-blocking pairs of polyhedra, Math. Program. 1 (1971) 168–194. doi:10.1007/BF01584085

[3] F. Jaeger, Flows and generalized coloring theorems in graphs, J. Combin. Theory Ser. B 26 (1979) 205–216. doi:10.1016/0095-8956(79)90057-1

[4] L. Jin and E. Steffen, Petersen cores and the oddness of cubic graphs, J. Graph Theory 84 (2017) 109–120. doi:10.1002/jgt.22014

[5] T. Kaiser and A. Raspaud, Perfect matchings with restricted intersection in cubic graphs, European J. Combin. 31 (2010) 1307–1315. doi:10.1016/j.ejc.2009.11.007

[6] D. Král’, E. Máčajová, O. Pangrác, A. Raspaud, J.-S. Sereni and M. Škoviera, Projective, affine, and abelian colorings of cubic graphs, European J. Combin. 30 (2009) 53–69. doi:10.1016/j.ejc.2007.11.029

[7] R. Lukot’ka and J. Mazák, Weak oddness as an approximation of oddness and resistance in cubic graphs, arXiv:1602.02949v1 [math.CO] (2016).

[8] E. Máčajová and M. Škoviera, Fano colourings of cubic graphs and the Fulkerson Conjecture, Theoret. Comput. Sci. 349 (2005) 112–120. doi:10.1016/j.tcs.2005.09.034

[9] E. Máčajová and M. Škoviera, Sparsely intersecting perfect matchings in cubic graphs, Combinatorica 34 (2014) 61–94. doi:10.1007/s00493-014-2550-4

[10] G. Mazzuoccolo, New conjectures on perfect matchings in cubic graphs, Electron. Notes Discrete Math. 40 (2013) 235–238. doi:10.1016/j.endm.2013.05.042

[11] E. Steffen, 1- factor and cycle covers of cubic graphs, J. Graph Theory 78 (2015) 195–206. doi:10.1002/jgt.21798