Forbidden triples and traceability: A characterization
type: Item
instance of: scholarly article
title: Forbidden triples and traceability: A characterization
zbMATH Open document ID: 0935.05079
DOI: 10.1016/S0012-365X(99)00021-7
author: Ronald Gould
author: John M. Harris
published in: Discrete Mathematics
publication date: 2000-05-04T00:00:00Z
review text: All graphs investigated in the paper are simple ones. If \(G\) is a connected graph and \({\mathfrak F}\) is a family of connected graphs then \({\mathfrak F}\) is called a forbidden family if no induced subgraph of \(G\) is isomorphic to any graph in \({\mathfrak F}\) and \(G\) is said to be \({\mathfrak F}\)-free. A graph is said to be traceable if it contains a path that spans the vertex set. In two previous papers the authors have found four distinct families of triples of subgraphs which imply traceability when they are forbidden in sufficiently large graphs. These triples exist of claws \(K_{1,m}\) and of two additional graphs whose figures are illustrated in the paper. The first result (Theorem 2.1) is the introduction of a fifth such triple containing the claw \(K_{1,3}\) and further two graphs are sketched. The proof of this result is a very extensive one; the authors need 17 claims. In a further result (Theorem 3.1) a characterization of the triples of subgraphs that imply traceability when they are forbidden is given, and the authors show that these five families are all such families.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 1334480
zbMATH Keywords: families of forbidden subgraphs
zbMATH Keywords: connected graph
zbMATH Keywords: traceability
zbMATH Keywords: characterization
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
cites work: Q3918148
cites work: Characterizing forbidden pairs for hamiltonian properties
cites work: Q3992558
cites work: Q3838229
cites work: Traceability in graphs with forbidden triples of subgraphs
cites work: Hamiltonian results inK1,3-free graphs
full work available at URL: s0012-365x(99)00021-7
OpenAlex ID: W2109252973
description: scientific article; zbMATH DE number 1334480