Chordality and 2-factors in tough graphs

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

Research output: Book/ReportReportProfessional

8 Citations (Scopus)

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 languageUndefined
Place of PublicationEnschede
PublisherUniversiteit Twente
Number of pages9
ISBN (Print)0169-2690
DOIs
Publication statusPublished - 1998

Publication series

Name
PublisherElsevier
No.1-3
Volume99
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
Bauer, D. ; Katona, G.Y. ; Kratsch, D. ; Veldman, H.J. / Chordality and 2-factors in tough graphs. Enschede : Universiteit Twente, 1998. 9 p.
@book{4d5275e812fb4d7ebbaea164a3f23c51,
title = "Chordality and 2-factors in tough graphs",
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{\'a}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.",
keywords = "Toughness, IR-74368, METIS-141260, 2-factors, Chordal graphs",
author = "D. Bauer and G.Y. Katona and D. Kratsch and H.J. Veldman",
note = "Memorandum Faculteit TW, nr 1430",
year = "1998",
doi = "10.1016/S0166-218X(99)00142-0",
language = "Undefined",
isbn = "0169-2690",
publisher = "Universiteit Twente",
number = "1-3",

}

Bauer, D, Katona, GY, Kratsch, D & Veldman, HJ 1998, 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.

Enschede : Universiteit Twente, 1998. 9 p.

Research output: Book/ReportReportProfessional

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 -

Bauer D, Katona GY, Kratsch D, Veldman HJ. Chordality and 2-factors in tough graphs. Enschede: Universiteit Twente, 1998. 9 p. https://doi.org/10.1016/S0166-218X(99)00142-0