Dirac-type characterizations of graphs without long chordless cycles

被引：11

作者：

Chvátal, V ^{[1
]}

Rusu, I

Sritharan, R

机构：

[1] Rutgers State Univ, Dept Comp Sci, New Brunswick, NJ 08903 USA

[2] Univ Orleans, LIFO, Orleans, France

[3] Univ Dayton, Dept Comp Sci, Dayton, OH 45469 USA

来源：

DISCRETE MATHEMATICS | 2002年 / 256卷 / 1-2期

关键词：

triangulated graphs; induced paths; forbidden induced cycles;

D O I：

10.1016/S0012-365X(01)00166-2

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We call a chordless path nu(1)nu(2)...nu(i) simplicial if it does not extend into any chordless path nu(0)nu(1)nu(2)...nu(i)nu(i+1). Trivially, for every positive integer k, a graph contains no chordless cycle of length k + 3 or more if each of its nonempty induced subgraphs contains a simplicial path with at most k vertices; we prove the converse. The case of k = 1 is a classic result of Dirac. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：445 / 448

页数：4