Premium
The equivalence of two conjectures of Berge and Fulkerson
Author(s) -
Mazzuoccolo G.
Publication year - 2011
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20545
Subject(s) - combinatorics , mathematics , equivalence (formal languages) , cubic graph , graph , petersen graph , enhanced data rates for gsm evolution , discrete mathematics , line graph , graph power , computer science , voltage graph , telecommunications
Abstract Let G be a bridgeless cubic graph. Fulkerson conjectured that there exist six 1‐factors of G such that each edge of G is contained in exactly two of them. Berge conjectured that the edge‐set of G can be covered with at most five 1‐factors. We prove that the two conjectures are equivalent. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:125‐128, 2011