Premium
Toughness and the existence of k ‐factors
Author(s) -
Enomoto Hikoe,
Jackson Bill,
Katerinis P.,
Saito Akira
Publication year - 1985
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190090106
Subject(s) - combinatorics , mathematics , graph , integer (computer science) , discrete mathematics , computer science , programming language
A connected graph G is called t ‐tough if t · w(G ‐ S) ⩽ |S| for any subset S of V(G) with w(G ‐ S) > 1, where w(G ‐ S ) is the number of connected components of G ‐ S. We prove that every k ‐tough graph has a k ‐factor if k|G| is even and |G| ⩾ k + 1. This result, first conjectured by Chvátal, is sharp in the following sense: For any positive integer k and for any positive real number ε, there exists a (k ‐ ε)‐tough graph G with k|G| even and |G| ⩾ k + 1 which has no k ‐factor.