
Aharoni, Ron
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.




Keywords: cover; infinite graph; matching
Aharoni-Berger conjecture ★★★
Conjecture If
are matroids on
and
for every partition
of
, then there exists
with
which is independent in every
.








Keywords: independent set; matroid; partition
Strong colorability ★★★
Author(s): Aharoni; Alon; Haxell
Let be a positive integer. We say that a graph
is strongly
-colorable if for every partition of the vertices to sets of size at most
there is a proper
-coloring of
in which the vertices in each set of the partition have distinct colors.
Conjecture If
is the maximal degree of a graph
, then
is strongly
-colorable.




Keywords: strong coloring
