Chordality and 2-factors in tough graphs

Chordality and 2-factors in tough graphs

0.00 Avg rating0 Votes
Article ID: iaor20012911
Country: Netherlands
Volume: 99
Issue: 1/3
Start Page Number: 323
End Page Number: 329
Publication Date: Feb 2000
Journal: Discrete Applied Mathematics
Authors: , , ,
Abstract:

A graph G is chordal if it contains no chordless cycle of length at least four and is k-chordal if a longest chordless cycle in G has length at most k. In this note it is proved that all 3/2-tough 5-chordal graphs have a 2-factor. This result is best possible in two ways. Examples due to Chvátal show that for all •>0 there exists a (3/2-•) -tough chordal graph with no 2-factor. Furthermore, examples due to Bauer and Schmeichel show that the result is false for 6-chordal graphs.

Reviews

Required fields are marked *. Your email address will not be published.