论文标题
Ryser猜想的概括和增强
Generalizations and strengthenings of Ryser's conjecture
论文作者
论文摘要
Ryser的猜想说，对于每一个$ r $ $ $ - 局部超graph $ h $，带有匹配的数字$ν（h）$，顶点封面号最多为$（r-1）ν（h）$。对König定理的这种概括仅以$ r \ leq 3 $或$ν（g）= 1 $和$ r \ leq 5 $而闻名。 Ryser的猜想的同等表述是，在每个$ r $ $ $边缘的颜色中，独立数字$α（g）$，最多存在$（r-1）α（g）$单色连接的子图，覆盖$ g $的顶点集。 我们表明，后者的繁殖者猜想自然会导致多种强烈的猜想和对超图和多部分图的概括。关于这些概括和增强，我们调查已知结果，改善一些结果，并介绍了新的问题和结果的集合。
Ryser's conjecture says that for every $r$-partite hypergraph $H$ with matching number $ν(H)$, the vertex cover number is at most $(r-1)ν(H)$. This far reaching generalization of König's theorem is only known to be true for $r\leq 3$, or $ν(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 $α(G)$, there exists at most $(r-1)α(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.
