Perfect k‐line graphs and k‐total graphs
Van Bang Lê · Journal of Graph Theory · 1993
Abstract The concept of the line graph can be generalized as follows. The k‐line graph Lk(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 Lk(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. © 1993 John Wiley & Sons, Inc.