Three forbidden subgraphs for line graphs
type: Item
instance of: scholarly article
title: Three forbidden subgraphs for line graphs
zbMATH Open document ID: 1003.05092
DOI: 10.1016/S0012-365X(01)00459-9
author: Yuansheng Yang
author: Jianhua Lin
author: Chun-Li Wang
published in: Discrete Mathematics
publication date: 2002-08-29T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C30
zbMATH DE Number: 1792434
zbMATH Keywords: line graph
zbMATH Keywords: forbidden subgraph
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
full work available at URL: s0012-365x(01)00459-9
OpenAlex ID: W1990219340
Recommended article: Forbidden induced subgraphs for line graphs
Recommended article: Line graphs and forbidden induced subgraphs
Recommended article: Forbidden subgraphs for graphs with line graphs of crossing number \(\leq 1\)
Recommended article: Forbidden Subgraphs and 3-Colorings
Recommended article: Graph Classes and Forbidden Patterns on Three Vertices
Recommended article: Q3838229
Recommended article: 3-colourability and forbidden subgraphs
Recommended article: Obstructions for three-coloring graphs with one forbidden induced subgraph
Recommended article: Q4213895
Recommended article: Four forbidden subgraph pairs for Hamiltonicity of 3-connected graphs
description: scientific article; zbMATH DE number 1792434