Forbidden triples and traceability: A characterization (Q1301658)

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.