Let \(\mathcal{F}\) be a family of sets, and \(F\in \mathcal{F}.\) Then \( B\subset F\) is called a guard set of \(F\) if for all \(F^{\prime }\in \mathcal{ F}\) so that \(F^{\prime }\cap F\neq \emptyset ,\) and \(F^{\prime }\varsubsetneq F\) it is \(B\cap F^{\prime }\neq \emptyset .\) The following problem is studied. Given a graph \(G.\) Find a family of sets \(\mathcal{F}\) such that \(G\) is the intersection graph of \(\mathcal{F}\) and the guard sets of all \(F\in \mathcal{F}\) are as small as possible. It is shown that the minimum is attained by the dual of the clique hypergraph of \(G.\)
- Contractions and minimal k-colorability
- scientific article; zbMATH DE number 3758364 (Why is no real title available?)
- scientific article; zbMATH DE number 25263 (Why is no real title available?)
- Normal hypergraphs and the perfect graph conjecture
- The cost chromatic number and hypergraph parameters
- The Representation of a Graph by Set Intersections
This page was built for publication: Optimal guard sets and the Helly property
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q607361)
