ON GRAPHS WITH LIMITED NUMBER OF P₄-PARTNERS

Abstract

The study of graphs containing few P 4 's generated an important number of results related to perfection, recognition, optimization problems (see [12], [15], [8]). We define here a new, larger class of graphs and show that the indicated problems may be efficiently solved on this class too (thus generalizing some of the previous results). Namely, we give a linear time recognition algorithm for this class and we note that the optimization problems concerning the clique number, stability number, chromatic number and clique cover number are solvable in linear time.