REVIEW
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Generalizations and strengthenings of Ryser's conjecture
read the original abstract
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\"onig's theorem is only known to be true for $r\leq 3$, or $\nu(G)=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.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.