TOPICS

# Šoltés Graphs

Šoltés (1994) proved that a connected graph with at least nine vertices is a line graph iff it does not contain any of seven given graphs as a forbidden induced subgraph, and furthermore that the number seven cannot be reduced even if the number of vertices is increased.

Šoltés (1994) labels the Beineke graphs as illustrated above and notes that these forbidden subgraphs have different roles in Beineke's characterization of line graphs (Beineke 1968). In particular, if the one of the graphs - is omitted, the class of graphs having the remaining graphs as forbidden subgraphs will contain infinitely many connected graphs which are not line graphs. On the other hand, omitting both graphs and yields a class containing only five connected non-line graphs.

Šoltés (1994) then establishes that a graph is a line graph iff

1. it does not contain any of the graphs - as an induced subgraph and is not ,

2. it does not contain any of the graphs - and as an induced subgraph and is neither nor , or

3. it does not contain any of the graphs - as an induced subgraph and is not isomorphic to any of the graphs , , , , and .

Finally, Šoltés (1994) shows that each of the five graph illustrated above contains exactly one of the graphs as an induced subgraph. Note that in the case of , an edge across the diamond that was omitted in the published paper has been added.

Beineke Graphs, Line Graph, Metelsky Graphs

## Explore with Wolfram|Alpha

More things to try:

## References

Beineke, L. W. "Derived Graphs and Digraphs." In Beiträge zur Graphentheorie (Ed. H. Sachs, H. Voss, and H. Walther). Leipzig, Germany: Teubner, pp. 17-33, 1968.Šoltés, Ľ. "Forbidden Induced Subgraphs for Line Graphs." Disc. Math. 132, 391-394, 1994.

## Cite this as:

Weisstein, Eric W. "Šoltés Graphs." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SoltesGraphs.html