Characterization and recognition of generalized clique-Helly graphs (Q2462382): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.dam.2007.06.013 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1979845124 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Duality and perfection for edges in cliques / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3941433 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4099676 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4088860 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graph Classes: A Survey / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Eduard Helly (1884-1943), in memoriam / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5708531 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The complexity of theorem-proving procedures / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5341481 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graph-Theoretic Concepts in Computer Science / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The edge intersection graphs of paths in a tree / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4288086 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4867717 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Clique-inverse graphs ofK3-free andK4-free graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4940014 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Extremal bi-Helly families / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4842710 / rank | |||
Normal rank |
Latest revision as of 13:44, 27 June 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