Generalizations and strengthenings of Ryser's conjecture
The electronic journal of combinatorics, Tome 28 (2021) no. 4
Ryser's conjecture says that for every $r$-partite hypergraph $H$ with matching number $\nu(H)$, the vertex cover number is at most $(r-1)\nu(H)$. This far-reaching generalization of König's theorem is only known to be true for $r\leq 3$, or when $\nu(H)=1$ and $r\leq 5$. An equivalent formulation of Ryser's conjecture is that in every $r$-edge coloring of a graph $G$ with independence number $\alpha(G)$, there exists at most $(r-1)\alpha(G)$ monochromatic connected subgraphs which cover the vertex set of $G$. We make the case that this latter formulation of Ryser's conjecture naturally leads to a variety of stronger conjectures and generalizations to hypergraphs and multipartite graphs. Regarding these generalizations and strengthenings, we survey the known results, improving upon some, and we introduce a collection of new problems and results.
@article{10_37236_9914,
author = {Louis DeBiasio and Yigal Kamel and Grace McCourt and Hannah Sheats},
title = {Generalizations and strengthenings of {Ryser's} conjecture},
journal = {The electronic journal of combinatorics},
year = {2021},
volume = {28},
number = {4},
doi = {10.37236/9914},
zbl = {1486.05195},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9914/}
}
TY - JOUR AU - Louis DeBiasio AU - Yigal Kamel AU - Grace McCourt AU - Hannah Sheats TI - Generalizations and strengthenings of Ryser's conjecture JO - The electronic journal of combinatorics PY - 2021 VL - 28 IS - 4 UR - http://geodesic.mathdoc.fr/articles/10.37236/9914/ DO - 10.37236/9914 ID - 10_37236_9914 ER -
Louis DeBiasio; Yigal Kamel; Grace McCourt; Hannah Sheats. Generalizations and strengthenings of Ryser's conjecture. The electronic journal of combinatorics, Tome 28 (2021) no. 4. doi: 10.37236/9914
Cité par Sources :