Š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 G_1-G_7 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 G_8 and G_9 yields a class containing only five connected non-line graphs.


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

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

2. it does not contain any of the graphs G_1-G_7 and G_9 as an induced subgraph and G is neither G_8 nor H_1, or

3. it does not contain any of the graphs G_1-G_7 as an induced subgraph and G is not isomorphic to any of the graphs G_8, G_9, H_1, H_2, and H_3.


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

See also

Beineke Graphs, Line Graph, Metelsky Graphs

Explore with Wolfram|Alpha


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.

Subject classifications