![](/files/happy5.png)
cover
Strong matchings and covers ★★★
Author(s): Aharoni
Let be a hypergraph. A strongly maximal matching is a matching
so that
for every matching
. A strongly minimal cover is a (vertex) cover
so that
for every cover
.
Conjecture If
is a (possibly infinite) hypergraph in which all edges have size
for some integer
, then
has a strongly maximal matching and a strongly minimal cover.
![$ H $](/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png)
![$ \le k $](/files/tex/26d614fff037e5976f481eab5b4e36c487e120ac.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ H $](/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png)
Keywords: cover; infinite graph; matching
Decomposing eulerian graphs ★★★
Author(s):
Conjecture If
is a 6-edge-connected Eulerian graph and
is a 2-transition system for
, then
has a compaible decomposition.
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ P $](/files/tex/b2b0b759db4d5a1b3204c38cdee6d9bd9e0d0dab.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ (G,P) $](/files/tex/fd3ab98e5fb37dd2a932a24c976ad96933b74a0e.png)
Faithful cycle covers ★★★
Author(s): Seymour
Conjecture If
is a graph,
is admissable, and
is even for every
, then
has a faithful cover.
![$ G = (V,E) $](/files/tex/5969f28fd067291799f25ca43b6642feb6b04bd0.png)
![$ p : E \rightarrow {\mathbb Z} $](/files/tex/acf577dca5adcf9fd9f7fb631a68262035044887.png)
![$ p(e) $](/files/tex/fa56cd603dd6dbffa93ed375e6a002107e59c9bb.png)
![$ e \in E(G) $](/files/tex/730c5d64c8d749c640adc18eb493c641ff1addc9.png)
![$ (G,p) $](/files/tex/d9c8f5e55f04622be55791c713068d286259ce27.png)
(m,n)-cycle covers ★★★
Author(s): Celmins; Preissmann
Conjecture Every bridgeless graph has a (5,2)-cycle-cover.
Cycle double cover conjecture ★★★★
Conjecture For every graph with no bridge, there is a list of cycles so that every edge is contained in exactly two.
![Syndicate content Syndicate content](/misc/feed.png)