Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: On the maximum fraction of edges covered by t perfect matchings in a
  cubic bridgeless graph   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.

0
The categories of this paper are: hep-ph
28
The categories of this paper are: alg-geom
25
The categories of this paper are: patt-sol
13
The categories of this paper are: quant-ph
1
The categories of this paper are: cs
16
The categories of this paper are: stat
23
The categories of this paper are: solv-int
34
The categories of this paper are: chem-ph
20
The categories of this paper are: acc-phys
18
The categories of this paper are: econ
14
The categories of this paper are: math-ph
6
The categories of this paper are: astro-ph
36
The categories of this paper are: cmp-lg
33
The categories of this paper are: plasm-ph
7
The categories of this paper are: hep-th
3
The categories of this paper are: physics