# Chordality and 2-factors in tough graphs

D. Bauer, G.Y. Katona, D. Kratsch, H.J. Veldman

Research output: Book/ReportReportOther research output

## Abstract

A graph $G$ is {\it chordal} if it contains no chordless cycle of length at least four and is {\it 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 Chvatal show that for all $\epsilon > 0$ there exists a $(3/2 - \epsilon)$-tough chordal graph with no $2$-factor. Furthermore, examples due to Bauer and Schmeichel show that the result is false for $6$-chordal graphs.
Original language Undefined Enschede University of Twente, Department of Applied Mathematics Published - 1998 Yes

• MSC-68R10
• EWI-3250
• MSC-05C38