Elsevier

Discrete Mathematics

Volume 132, Issues 1–3, 15 September 1994, Pages 391-394
Discrete Mathematics

Note
Forbidden induced subgraphs for line graphs

https://doi.org/10.1016/0012-365X(92)00577-EGet rights and content
Under an Elsevier user license
open archive

Abstract

We prove that a connected graph with at least nine vertices is a line graph if and only if it does not contain any of the seven given graphs as an induced subgraph. We also show that the number seven cannot be reduced even if the number of vertices is increased.

Cited by (0)