Three forbidden subgraphs for line graphs (Q1613508): Difference between revisions
From MaRDI portal
Changed an Item |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0012-365x(01)00459-9 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1990219340 / rank | |||
Normal rank |
Latest revision as of 10:23, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Three forbidden subgraphs for line graphs |
scientific article |
Statements
Three forbidden subgraphs for line graphs (English)
0 references
29 August 2002
0 references
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.
0 references
line graph
0 references
forbidden subgraph
0 references