Three forbidden subgraphs for line graphs (Q1613508): Difference between revisions

Beineke has shown that a connected graph \(G\) is a line graph iff it does not contain any of nine graphs drawn in a figure as an induced subgraph. This result was improved by Šoltés: \(G\) is a line graph if it does not contain any of the first seven graphs given by Beineke as an induced subgraph and is not isomorphic to any of five additional drawn graphs. The present authors construct three graphs with the property that a 3-connected graph with minimum degree at least 7 is a line graph iff it does not contain any of the three graphs as an induced subgraph (Theorem 3). This statement is proved by disproving a conjecture of Šoltés which he had concluded from his above-mentioned result. The present authors also show that the number of excluded subgraphs cannot be reduced, no matter that connectivity is specified.