Chordality and 2-Factors in Tough Graphs

AgraphG 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.Inthis 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 Chvatal 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 6chordal graphs. Keywords : toughness, 2-factors, chordal graphs AMS Subject Classifications (1991) : 68R10, 05C38 # Supported in part by NATO Collaborative Research Grant CRG 921251. + Supported in part by Hungarian National Foundation for Scientific Research, OTKA Grant Numbers F 014919 and T 014302. 1 1 Introduction We begin with a few definitions and some notation. Other definitions will be given later, as needed. A good reference for any undefined terms is [7]. We consider only undirected graphs with no loops or ..