最小度限制下图的分解

一、背景和记号 本文所说的图均指有限,无向,无环和无多重边的简单图。 Gyy等人提出这样一个问题:对于给定的自然数对s,t,是否存在(最小的)自然数f(s,t),使得每个连通度至少是f(s,t)的图,其顶点集可以划分为两个集,这两个集的导出子图的连通度分别至少是s,t。为了解决这个问题,Thomassen提出一个相类比的问题:对于给定的自然数对s,t;是否存在(最小的)自然数g(s,t),使得每个最小度至少是g(s,t)的图,其顶点集可以划分为两个集,这两个集的导出子图的最小度分别至少是s和t。