Premium
On decomposition of triangle‐free graphs under degree constraints
Author(s) -
Kaneko Atsushi
Publication year - 1998
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/(sici)1097-0118(199801)27:1<7::aid-jgt2>3.0.co;2-u
Subject(s) - combinatorics , mathematics , degree (music) , vertex (graph theory) , graph , discrete mathematics , independent set , physics , acoustics
We prove that if s and t are positive integers and if G is a triangle‐free graph with minimum degree s + t , then the vertex set of G has a decomposition into two sets which induce subgraphs of minimum degree at least s and t , respectively. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 7–9, 1998