Kühn, Daniella


Simultaneous partition of hypergraphs ★★

Author(s): Kühn; Osthus

\begin{problem} Let $H_1$ and $H_2$ be two $r$-uniform hypergraph on the same vertex set $V$. Does there always exist a partition of $V$ into $r$ classes $V_1, \dots , V_r$ such that for both $i=1,2$, at least $r!m_i/r^r -o(m_i)$ hyperedges of $H_i$ meet each of the classes $V_1, \dots , V_r$? \end{problem}

Keywords:

Complexity of the H-factor problem. ★★

Author(s): Kühn; Osthus

An $H$-factor in a graph $G$ is a set of vertex-disjoint copies of $H$ covering all vertices of $G$. \begin{problem}Let $c$ be a fixed positive real number and $H$ a fixed graph. Is it NP-hard to determine whether a graph $G$ on $n$ vertices and minimum degree $cn$ contains and $H$-factor?% Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. \end{problem}

Keywords:

Syndicate content