On partitions of K2, 3-free graphs under degree constraints
On partitions of K2, 3-free graphs under degree constraints
复制标题
DOI：
10.1016/j.disc.2018.08.015
复制
发表时间：
2018-12
期刊：
影响因子：
--
通讯作者：
Jianfeng Hou;Huawen Ma;Jiguo Yu;Xia Zhang
中科院分区：
文献类型：
--
作者：
Jianfeng Hou;Huawen Ma;Jiguo Yu;Xia Zhang
设s，t是两个正整数，n是一组图.设g（s，t; n）是最小整数g，使得任何最小度至少为g的无图可划分为两个集合，其中导出子图的最小度分别为s和t.对于一个给定的图H，我们简单地写g（s，t; H）为g（s，t; H），当H ={H}。本文证明了：若s，t≥ 2，则g（s，t; K2，3）≤ s+ t且g（s，t;{K3，C8，K2，3}）≤ s+ t− 1.此外，如果K 4− e的一个顶点与K 4− e的两个顶点相连而得到的图的集合是G，则至少有五个顶点的无G图上的g（s，t; G）≤ s+ t，这推广了Liu和Xu（2017）的结果。
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; K 2, 3)≤ s+ t and g (s, t;{K 3, C 8, K 2, 3})≤ s+ t− 1. Moreover, if ℋ is the set of graphs obtained by connecting a single vertex to exactly two vertices of K 4− e, then g (s, t; ℋ)≤ s+ t on ℋ-free graphs with at least five vertices, which generalize a result of Liu and Xu (2017).