ries bernard - Search Results

Detecting strong cliques

Hujdurovic, Ademir ; Milanic, Martin ; Ries, Bernard

In: Discrete Mathematics, 2019, vol. 342, no. 9, p. 2738-2750

A strong clique in a graph is a clique intersecting every maximal independent set. We study the computational complexity of six algorithmic decision problems related to strong cliques in graphs and almost completely determine their complexity in the classes of chordal graphs, weakly chordal graphs, line graphs and their complements, and graphs of maximum degree at most three. Our results rely...

OPEN IN
SONAR

Graphs vertex-partitionable into strong cliques

Hujdurović, Ademir ; Milanič, Martin ; Ries, Bernard

In: Discrete Mathematics, 2018, vol. 341, p. 1392-1405

A clique in a graph is strong if it intersects all maximal independent sets. A graph is localizable if it has a partition of the vertex set into strong cliques. Localizable graphs were introduced by Yamashita and Kameda in 1999 and form a rich class of well- covered graphs that coincides with the class of well-covered graphs within the class of perfect graphs. In this paper, we give several...

Refine my results

Document type

Institution

Specific Collection

Language

Author