论文部分内容阅读
一个非平凡图G的点荫度a（G）是一个最小图顶点划分数使得每一个划分集的导出子图是一个森林．近年来对点荫度的研究成为图论的一个焦点并且关于这个问题有更深一步的发展，例如，随机图的点荫度以分式点荫度等．得到一个关于平面图的点荫度的一个上界；如果平面图G是没有3-圈，或是没有4-圈，或是没有5-圈，那么G的点荫度不超过2．研究的起因是一个著名的猜想：任何3-可着色的平面图的点荫度不超过2．四色定理是图论中最著名的一个定理，伴随产生了一个问题，那就是什么样的平面图是3-可着色的．不幸，这是一个难问题，Garey等