30
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      On the maximum fraction of edges covered by t perfect matchings in a cubic bridgeless graph

      Preprint
      ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          A conjecture of Berge and Fulkerson (1971) states that every cubic bridgeless graph contains 6 perfect matchings covering each edge precisely twice, which easily implies that every cubic bridgeless graph has three perfect matchings with empty intersection (this weaker statement was conjectured by Fan and Raspaud in 1994). Let \(m_t\) be the supremum of all reals \(\alpha\le 1\) such that for every cubic bridgeless graph \(G\), there exist \(t\) perfect matchings of \(G\) covering a fraction of at least \(\alpha\) of the edges of \(G\). It is known that the Berge-Fulkerson conjecture is equivalent to the statement that \(m_5=1\), and implies that \(m_4=\tfrac{14}{15}\) and \(m_3=\tfrac45\). In the first part of this paper, we show that \(m_4=\tfrac{14}{15}\) implies \(m_3=\tfrac45\), and \(m_3=\tfrac45\) implies the Fan-Raspaud conjecture, strengthening a recent result of Tang, Zhang, and Zhu. In the second part of the paper, we prove that for any \(2\le t \le 4\) and for any real \(\tau\) lying in some appropriate interval, deciding whether a fraction of more than (resp. at least) \(\tau\) of the edges of a given cubic bridgeless graph can be covered by \(t\) perfect matching is an NP-complete problem. This resolves a conjecture of Tang, Zhang, and Zhu.

          Related collections

          Author and article information

          Journal
          2013-06-12
          2015-03-10
          Article
          1306.2828
          03a9af67-0e05-4f54-b340-05e9459216dc

          http://arxiv.org/licenses/nonexclusive-distrib/1.0/

          History
          Custom metadata
          13 pages, 5 figures - revised version
          math.CO

          Combinatorics
          Combinatorics

          Comments

          Comment on this article