Graphs vertex-partitionable into strong cliques
- Hujdurović, Ademir University of Primorska, Koper, Slovenia
- Milanič, Martin University of Primorska, Koper, Slovenia
- Ries, Bernard Université de Fribourg, Fribourg, Switzerland
-
2018
Published in:
- Discrete Mathematics. - 2018, vol. 341, p. 1392-1405
English
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 nonperfect graph classes: triangle-free graphs, C4-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 k-partite well-covered graphs having all maximal cliques of size k.
- Faculty
- Faculté des sciences économiques et sociales et du management
- Department
- Département d'informatique
- Language
-
- English
- Classification
- Computer science and technology
- License
- License undefined
- Identifiers
-
- RERO DOC 324601
- DOI 10.1016/j.disc.2018.02.013
- Persistent URL
- https://folia.unifr.ch/unifr/documents/307834
Statistics
Document views: 23
File downloads:
- vertexpartitionable_rero.pdf: 101