Dirac-type characterizations of graphs without long chordless cycles
All graphs considered in this note are undirected, simple, and finite ones, and induced cycles and induced paths are called chordless cycles and chordless paths. Let \(P_i\) be a path with precisely \(i\) vertices. Then a chordless path \(v_1v_2\dots v_i\) with at least one vertex is called simplicial if it does not extend into any chordless path \(v_0v_1v_2\dots v_iv_{i+1}\). The authors yield a generalization of a classic theorem of Dirac from 1961 and they prove the following structural properties: (1) For every positive integer \(k\), a graph contains no chordless cycle of length \(k+3\) or more iff each of its nonempty induced subgraphs \(G\) has the following property: If \(G\) contains a vertex \(v\) and a chordless \(P_k\) with all \(k\) vertices distinct from \(v\) and nonadjacent to \(v\), then it contains a simplicial \(P_k\) with all \(k\) vertices distinct from \(v\) and nonadjacent to \(v\) (Theorem 1). (2) For every positive integer \(k\), a graph contains no chordless cycle of length \(k+3\) or more iff each of its nonempty induced subgraphs contains a simplicial path with at most \(k\) vertices (Theorem 2). At the end of this note we find similar results of other authors.
scientific article; zbMATH DE number 1838939