Dirac-type characterizations of graphs without long chordless cycles (Q1849953): Difference between revisions

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.