RECOGNITION ALGORITM FOR P₄-TIDY GRAPHS
MIHAI TALMACIU
Department of Mathematics, Informatics and Education Sciences, Faculty of Sciences, "Vasile Alecsandri" University of Bacău, 157 Calea Mărăşeşti, 600115 Bacău, ROMANIA, e-mail: mtalmaciu@ub.ro, mihaitalmaciu@yahoo.com
Abstract
In this article we give a characterization of P₄-tidy graphs. We also give recognition algorithm for P₄-tidy graphs, comparable to existent ones as execution time. Finally, we determine the combinatorial optimization number in efficient time for P₄-tidy graphs. We show that for P4-tidy graphs clique problem is polynomial time.