Article ID Journal Published Year Pages File Type
9514432 Discrete Mathematics 2018 8 Pages PDF
Abstract
Suppose that s, t are two positive integers, and ℋ is a set of graphs. Let g(s,t;ℋ) be the least integer g such that any ℋ-free graph with minimum degree at least g can be partitioned into two sets which induced subgraphs have minimum degree at least s and t, respectively. For a given graph H, we simply write g(s,t;H) for g(s,t;ℋ) when ℋ={H}. In this paper, we show that if s,t≥2, then g(s,t;K2,3)≤s+t and g(s,t;{K3,C8,K2,3})≤s+t−1. Moreover, if ℋ is the set of graphs obtained by connecting a single vertex to exactly two vertices of K4−e, then g(s,t;ℋ)≤s+t on ℋ-free graphs with at least five vertices, which generalize a result of Liu and Xu (2017).
Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , ,