Hardly perfect graphs.

Published in Volume XIV, 2004, pages 12-22

Authors: Cornelius CROITORU, Cristian FRASINARU, Elefterie OLARU, Mihai TALMACIU

Abstract

We call a graph $G$ {it hardly perfect} if for each its induced subgraph $G’$ there is an optimal coloring of $G$ assigning to the vertices of $G’$ a number of colors equal to the maximum cardinality of a clique in $G’$ which can be extended to a maximum clique of $G$. In this paper the combinatorial structure of hardly perfect graphs is completely described. Using the characterization theorem and the fact that hardly perfect graphs are $P4$-free, we were able to design a recognition algorithm with linear time complexity.

Bibtex

@article{sacscuza:croitoru2004hpg,
  title={Hardly perfect graphs.},
  author={Cornelius CROITORU and Cristian FRASINARU and Elefterie OLARU and Mihai TALMACIU},
  journal={Scientific Annals of Computer Science},
  volume={14},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2004},
  pages={12--22},
  publisher={``A.I. Cuza'' University Press}
}