Article ID Journal Published Year Pages File Type
4651229 Discrete Mathematics 2006 5 Pages PDF
Abstract

A graph G   is called K1,nK1,n-free if G   has no induced subgraph isomorphic to K1,nK1,n. Let n, a, b   be integers with n⩾3n⩾3, a⩾1a⩾1, and a⩽b⩽a(n-2)+1a⩽b⩽a(n-2)+1. We prove that every connected K1,nK1,n-free graph G   has a connected [a,b+n-⌈b/a⌉][a,b+n-⌈b/a⌉]-factor if G   contains an [a,b][a,b]-factor. This result is sharp in the sense that there exists a connected K1,nK1,n-free graph which has an [a,b][a,b]-factor but no connected [a,b+n-⌈b/a⌉-1][a,b+n-⌈b/a⌉-1]-factor for b⩽a(n-2)+1b⩽a(n-2)+1.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,