### 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 ..-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 (..-ε)-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 |
---|---|

Place of Publication | Enschede |

Publisher | Universiteit Twente |

Number of pages | 9 |

ISBN (Print) | 0169-2690 |

DOIs | |

Publication status | Published - 1998 |

### Publication series

Name | |
---|---|

Publisher | Elsevier |

No. | 1-3 |

Volume | 99 |

ISSN (Print) | 0012-365X |

### Keywords

- Toughness
- IR-74368
- METIS-141260
- 2-factors
- Chordal graphs

## Cite this

Bauer, D., Katona, G. Y., Kratsch, D., & Veldman, H. J. (1998).

*Chordality and 2-factors in tough graphs*. Enschede: Universiteit Twente. https://doi.org/10.1016/S0166-218X(99)00142-0