### Abstract

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

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

}

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

**Chordality and 2-factors in tough graphs.** / Bauer, D.; Katona, G.Y.; Kratsch, D.; Veldman, H.J.

Research output: Book/Report › Report › Professional

TY - BOOK

T1 - Chordality and 2-factors in tough graphs

AU - Bauer, D.

AU - Katona, G.Y.

AU - Kratsch, D.

AU - Veldman, H.J.

N1 - Memorandum Faculteit TW, nr 1430

PY - 1998

Y1 - 1998

N2 - 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.

AB - 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.

KW - Toughness

KW - IR-74368

KW - METIS-141260

KW - 2-factors

KW - Chordal graphs

U2 - 10.1016/S0166-218X(99)00142-0

DO - 10.1016/S0166-218X(99)00142-0

M3 - Report

SN - 0169-2690

BT - Chordality and 2-factors in tough graphs

PB - Universiteit Twente

CY - Enschede

ER -