Premium
Perfect k ‐line graphs and k ‐total graphs
Author(s) -
Lê Van Bang
Publication year - 1993
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190170108
Subject(s) - combinatorics , mathematics , line graph , discrete mathematics , vertex transitive graph , perfect graph , block graph , split graph , chordal graph , symmetric graph , graph , pathwidth , graph power , voltage graph
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. © 1993 John Wiley & Sons, Inc.