Toughness and the existence of k-factors. (English) Zbl 0598.05054

Enomoto, Hikoe; Jackson, Bill; Katerinis, P.; Saito, Akira

J. Graph Theory 9, No. 1, 87-95 (1985).

Finite undirected connected graphs G without loops and multiple edges are considered. If \(S\subset V(G)\), then by G-S denote the subgraph of G induced by the set V(G)-S and by w(G-S) the number of components of G-S.
A graph G is t-tough if the implication \(w(G-S)>1\Rightarrow | S| \geq t.w(G-S)\) holds for any \(S\subset V(G)\). The toughness of a graph was introduced by V. Chvátal who made also the following conjecture [Tough graphs and Hamiltonian circuits, Discrete Math. 5, 215-228 (1973; Zbl 0256.05122)]: If G is k-tough, \(| G| \geq k+1\) and \(k| G|\) is even, then G has a k-factor.
The main result of the present paper is the proof of this conjecture (Theorem 1). Further, the result is shown to be sharp: (Theorem 3): For \(k\geq 1\) and any positive \(\epsilon\), there exists a (k-\(\epsilon)\)-tough graph with \(k| G|\) even, \(| G| \geq k+1\) which has no k- factor.

Reviewer: St.Znám

MSC:

05C70

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Keywords:

toughness; k-factor

Citations:

Zbl 0256.05122

References:

[1]	, and , Graphs & Digraphs. Prindle, Weber & Schmidt, Massachusetts (1979).
[2]	and , Graph Theory with Applications. Macmillan, London (1976). · Zbl 1226.05083
[3]	Chvátal, Discrete Math. 5 pp 215– (1973)
[4]	Nearly k-tough graphs with no k-factor, unpublished.
[5]	Tutte, Canad. J. Math. 4 pp 314– (1952) · Zbl 0049.24202