Dirac-type characterizations of graphs without long chordless cycles (Q1849953): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 05:55, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Dirac-type characterizations of graphs without long chordless cycles |
scientific article |
Statements
Dirac-type characterizations of graphs without long chordless cycles (English)
0 references
2 December 2002
0 references
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.
0 references
forbidden induced cycles
0 references
chordless paths
0 references