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 languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Publication statusPublished - 1998
Externally publishedYes

Keywords

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

Cite this