C‐perfect hypergraphs

Abstract Let \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\mathcal{H}}=({{X}},{\mathcal{E}})$\end{document} be a hypergraph with vertex set X and edge set \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\mathcal{E}}$\end{document} . A C‐coloring of \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\mathcal{H}}$\end{document} is a mapping ϕ : X →ℕ such that | ϕ ( E )|<| E | holds for all edges \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${{E}}\in{\mathcal{E}}$\end{document} (i.e. no edge is multicolored). We denote by \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}$\bar{\chi}({\mathcal{H}})$\end{document} the maximum number | ϕ ( X )| of colors in a C‐coloring. Let further \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}$\alpha({\mathcal{H}})$\end{document} denote the largest cardinality of a vertex set S ⊆ X that contains no \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${{E}}\in{\mathcal{E}}$\end{document} , and \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}$\tau({\mathcal{H}})=|{{X}}|-\alpha({\mathcal{H}})$\end{document} the minimum cardinality of a vertex set meeting all \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document} $E \in {\mathcal{E}}$\end{document} . The hypergraph \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document} ${\mathcal{H}}$\end{document} is called C‐perfect if \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document} $\bar{\chi}({\mathcal{H}}\prime)=\alpha({\mathcal{H}}\prime)$\end{document} holds for every induced subhypergraph \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\mathcal{H}}\prime\subseteq{\mathcal{H}}$\end{document} . If \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\mathcal{H}}$\end{document} is not C‐perfect but all of its proper induced subhypergraphs are, then we say that it is minimally C‐imperfect. We prove that for all r, k ∈ℕ there exists a finite upper bound h ( r, k ) on the number of minimally C‐imperfect hypergraphs \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\mathcal{H}}$\end{document} with \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}$\tau({\mathcal{H}})\le {{k}}$\end{document} and without edges of more than r vertices. We give a characterization of minimally C‐imperfect hypergraphs that have τ=2, which also characterizes implicitly the C‐perfect ones with τ=2. From this result we derive an infinite family of new constructions that are minimally C‐imperfect. A characterization of minimally C‐imperfect circular hypergraphs is presented, too. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 132–149, 2010