Journal article

Graphs vertex-partitionable into strong cliques

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.
Faculté des sciences économiques et sociales
Département d'informatique
  • English
Computer science
License undefined
Persistent URL

Document views: 8 File downloads:
  • vertexpartitionable_rero.pdf: 45