Dirac-type characterizations of graphs without long chordless cycles
type: Item
instance of: scholarly article
title: Dirac-type characterizations of graphs without long chordless cycles
zbMATH Open document ID: 1011.05050
DOI: 10.1016/S0012-365X(01)00166-2
author: Vašek Chvátal
author: Irena Rusu
author: R. Sritharan
published in: Discrete Mathematics
publication date: 2002-12-02T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1838939
zbMATH Keywords: forbidden induced cycles
zbMATH Keywords: chordless paths
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
full work available at URL: s0012-365x(01)00166-2
OpenAlex ID: W2035943952
description: scientific article; zbMATH DE number 1838939