PERFECT K-LINE GRAPHS AND K-TOTAL GRAPHS

The concept of the line graph can be generalized as follows The k-line graph L(k)(G) of a graph G is defined as a graph whose vertices are the complete subgraphs on k vertices in G. Two distinct such complete subgraphs are adjacent in L(k)(G) if and only if they have in G k - 1 vertices in common. The concept of the total graph can be generalized similarly. Then the Perfect Graph Conjecture will be proved for 3-line graphs and 3-total graphs. Moreover, perfect 3-line graphs are not contained in any of the known classes of perfect graphs.