Chordality and 2-factors in Tough Graphs
Chordality and 2-factors in Tough Graphs
复制标题
DOI：
10.1016/s0166-218x(99)00142-0
复制
发表时间：
2000-02
期刊：
影响因子：
--
通讯作者：
D. Bauer;G. Katona;D. Kratsch;H. J. Veldman
中科院分区：
文献类型：
--
作者：
D. Bauer;G. Katona;D. Kratsch;H. J. Veldman
一个图G是弦的，如果它不包含长度至少为4的无弦圈，并且是k -弦的，如果G中最长的无弦圈的长度至多为k。本文证明了3个2 -坚韧5-弦图都有2 -因子。这个结果在两个方面是最好的。Chvátal的例子表明，对于所有ε>0，存在一个没有2 -因子的（3 2-ε）-坚韧弦图。Bauer和Schmeichel给出的例子表明，对于6 -弦图，该结果是错误的.
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 3 2 -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 ( 3 2 −ε) -tough chordal graph with no 2 -factor. Furthermore, examples due to Bauer and Schmeichel show that the result is false for 6 -chordal graphs.