Aharoni, Ron

Strong matchings and covers ★★★

Author(s): Aharoni

Let $H$ be a \Def{hypergraph}. A \emph{strongly maximal} matching is a matching $F \subseteq E(H)$ so that $|F' \setminus F| \le |F \setminus F'|$ for every matching $F'$. A \emph{strongly minimal} cover is a (vertex) cover $X \subseteq V(H)$ so that $|X' \setminus X| \ge |X \setminus X'|$ for every cover $X'$.

\begin{conjecture} If $H$ is a (possibly infinite) hypergraph in which all edges have size $\le k$ for some integer $k$, then $H$ has a strongly maximal matching and a strongly minimal cover. \end{conjecture}

Keywords: cover; infinite graph; matching

Aharoni-Berger conjecture ★★★

Author(s): Aharoni; Berger

\begin{conjecture} If $M_1,\ldots,M_k$ are matroids on $E$ and $\sum_{i=1}^k rk_{M_i}(X_i) \ge \ell (k-1)$ for every partition $\{X_1,\ldots,X_k\}$ of $E$, then there exists $X \subseteq E$ with $|X| = \ell$ which is independent in every $M_i$. \end{conjecture}

Keywords: independent set; matroid; partition

Strong colorability ★★★

Author(s): Aharoni; Alon; Haxell

Let $r$ be a positive integer. We say that a graph $G$ is strongly $r$-colorable if for every partition of the vertices to sets of size at most $r$ there is a proper $r$-coloring of $G$ in which the vertices in each set of the partition have distinct colors.

\begin{conjecture} If $\Delta$ is the maximal degree of a graph $G$, then $G$ is strongly $2 \Delta$-colorable. \end{conjecture}

Keywords: strong coloring

Syndicate content