Graphs vertex-partitionable into strong cliques |
| |
Authors: | Ademir Hujdurović Martin Milanič Bernard Ries |
| |
Institution: | 1. University of Primorska, IAM, Muzejski trg 2, SI-6000 Koper, Slovenia;2. University of Primorska, FAMNIT, Glagolja?ka 8, SI-6000 Koper, Slovenia;3. University of Fribourg, Department of Informatics, Bd de Pérolles 90, CH-1700 Fribourg, Switzerland |
| |
Abstract: | 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 equivalent formulations of the property of localizability and develop polynomially testable characterizations of localizable graphs within three non-perfect graph classes: triangle-free graphs, -free graphs, and line graphs. Furthermore, we use localizable graphs to construct an infinite family of counterexamples to a conjecture due to Zaare-Nahandi about -partite well-covered graphs having all maximal cliques of size . |
| |
Keywords: | Strong clique Clique cover Well-covered graph Localizable graph Line graph Characterization |
本文献已被 ScienceDirect 等数据库收录! |
|