Characterization and recognition of generalized clique-Helly graphs (Q2462382): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: Jayme Luiz Szwarcfiter / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Dalibor Fronček / rank | |||
Normal rank |
Revision as of 20:17, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Characterization and recognition of generalized clique-Helly graphs |
scientific article |
Statements
Characterization and recognition of generalized clique-Helly graphs (English)
0 references
30 November 2007
0 references
For given \(p\geq 1\), \(q\geq 0\) a family of sets \(\mathcal F\) is \((p,q)\)-intersecting if every subfamily \(\mathcal F'\subseteq \mathcal F\) consisting of \(p\) or less members has total intersection cardinality at least \(q\). A family of sets \(\mathcal F\) is \((p,q)\)-Helly if every \((p,q)\)-intersecting subfamily \(\mathcal F'\subseteq \mathcal F\) has total intersection cardinality at least \(q\). A graph \(G\) is \((p,q)\)-clique-Helly if its family of (maximal) cliques is \((p,q)\)-Helly. This generalizes the notion of the Helly property and the clique-Helly graphs which correspond to the case when \(p=2\), \(q=1\). A characterization of \((p,q)\)-clique-Helly graphs is given. It is shown that for fixed \(p,q\) a polynomial-time recognition algorithm exists while for a variable \(p\) or \(q\) the recognition of \((p,q)\)-clique-Helly graphs is NP-hard.
0 references
Clique-Helly graphs
0 references
Helly property
0 references
intersecting sets
0 references