关于平面图点荫度的一点改进

作者：鲁晓旭; 许宝刚着色点荫度平面图

摘要：一个非平凡图G的点荫度a（G）是一个最小图顶点划分数使得每一个划分集的导出子图是一个森林．近年来对点荫度的研究成为图论的一个焦点并且关于这个问题有更深一步的发展，例如，随机图的点荫度以分式点荫度等．得到一个关于平面图的点荫度的一个上界；如果平面图G是没有3-圈，或是没有4-圈，或是没有5-圈，那么G的点荫度不超过2．研究的起因是一个著名的猜想：任何3-可着色的平面图的点荫度不超过2．四色定理是图论中最著名的一个定理，伴随产生了一个问题，那就是什么样的平面图是3-可着色的．不幸，这是一个难问题，Garey等人证明了判定一个平面图是否3-可着的即使在一个点不超过4的条件下仍然是NP-难问题．因此这个猜想是一个不易解决的，人们开始在一些特殊图上进行验证这个猜想是否正确．我们知道一个著名的定理：不含3-圈的平面图是3-可着色的．结合结果，给出猜想的一个正面的肯定．Havel给出两个反例，如果平面图含有4-圈或有5-圈是不可3-可着色的，因此4-圈和5-圈在证明平面图是3-可着色时必须排除．不过在结论中，如果平面图不含有4-圈或不含有5-圈，那么它的点荫度不超过2．从而可以看出猜想的条件还是很强的．同时我们的结果也拓宽了张忠辅等人的结果：外平图的点荫度不超过2．

注：因版权方要求，不能公开全文，如需全文，请咨询杂志社