
























Motivated by the analogous questions in graphs, we study the complexity of coloring and stable set problems in hypergraphs with forbidden substructures and bounded edge size. Letting $ν(G)$ denote the maximum size of a matching in $H$, we obtain complete dichotomies for the complexity of the following problems parametrized by fixed $r, k, s \in \mathbb{N}$: $r$-Coloring in hypergraphs $G$ with edge size at most $k$ and $ν(G) \leq s$; $r$-Precoloring Extension in $k$-uniform hypergraphs $G$ with $ν(G) \leq s$; $r$-Precoloring Extension in hypergraphs $G$ with edge size at most $k$ and $ν(G) \leq s$; Maximum Stable Set in $k$-uniform hypergraphs $G$ with $ν(G) \leq s$; Maximum Weight Stable Set in $k$-uniform hypergraphs with $ν(G) \leq s$; as well as partial results for $r$-Coloring in $k$-uniform hypergraphs $ν(G) \leq s$. We then turn our attention to $2$-Coloring in 3-uniform hypergraphs with forbidden induced subhypergraphs, and give a polynomial-time algorithm when restricting the input to hypergraphs excluding a fixed one-edge hypergraph. Finally, we consider linear 3-uniform hypergraphs (in which every two edges share at most one vertex), and show that excluding an induced matching in $G$ implies that $ν(G)$ is bounded by a constant; and that $3$-coloring linear $3$-uniform hypergraphs $G$ with $ν(G) \leq 532$ is NP-hard.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。