Hereditary Classes of Line Graphs

A.V. Gagarin 1, LE. Zverovich1
1 Department of Mechanics and Mathematics Belarus State University Minsk 220050 Republic of Belarus

Abstract

We investigate the connections between families of graphs closed under (induced) subgraphs and their forbidden (induced) subgraph characterizations. In particular, we discuss going from a forbidden subgraph characterization of a family \(\mathbb{P}\) to a forbidden induced subgraph characterization of the family of line graphs of members of \(\mathbb{P}\) in the most general case. The inverse problem is considered too.