论文部分内容阅读
假设G为有限简单图.V(G)和E(G)分别表示G的顶点集和边集,简记为V和E.令G1,...,Gm表示m个图类.如果V(G)可以被分解为m个集合V1,...,Vm,使得对于1≤l≤m,子图G[Vl]属于图类Gl,那么我们称其为图G的一个(G1,...,Gm)-分解.为简单起见,我们用F,I,?k和Fk分别表示图类森林,独立集,最大度为k的图和最大度为k的森林.图G的最大平均度定义如下:mad(G)=max{(2|E(H)|)/(|V(H)|):H?G}.用g(G)表示G的围长,即G中的最小圈的长度.若G为连通平面图,则有mad(G)<(2g(G))/(g(G)-2).2013年,对于任意的d1和d2,Montassier和Ochem构造了一个围长为g≥4且不存在(?d1,?d2)-分解的平面图.因此对于平面图的(?d1,?d2)-分解问题,人们主要考虑围长至少为5的平面图.之后,对于此类问题,Havet和Sereni证明了围长g≥5的平面图存在(?4,?4)-分解,Choi和Raspaud证明了围长g≥5的平面图存在(?3,?5)-分解.最后Borodin和Kostochka证明了围长g≥5的平面图存在(?2,?6)-分解.对于围长g≥6的平面图的(?d1,?d2)-分解问题,2014年,Borodin和Kostochka证明了若图G满足mad(G)≤(14)/5,则G存在(?1,?4)-分解.由此可得围长g≥6的平面图存在(?1,?4)-分解.另一方面,Borodin等人证明了对于任意的d,存在围长为6且不存在(I,?d)-分解的平面图.因此对于围长g≥7的平面图,研究它是否存在(I,?k)-分解(或(I,Fk)-分解)是非常有意义的.另一方面,在2014年,Borodin和Kostochka证明了若图G满足mad(G)≤8/3,则G存在(I,?2)-分解;若G满足mad(G)≤(16)/5,则G存在(I,?4)-分解.作为推论,我们有围长g≥7的平面图存在(I,?4)-分解及围长g≥8的平面图存在(I,?2)-分解.事实上,Montassier和Ochem证明了围长g≥7的平面图是否存在(I,?2)-分解是NP-完全问题.最近,Dross,Montassier和Pinlou考虑了上述图类的(I,Fk)-分解问题.他们证明了每一个围长g≥7的平面图都存在(I,F5)-分解;每一个围长g≥8的平面图都存在(I,F3)-分解.基于以上图分解问题的研究,本学位论文研究了围长限制条件下平面图的(Fi,Fj)-分解问题.论文框架结构及内容如下:在第一章中,我们先给出本文将用到的基本概念,再简述相关领域的研究现状和本文的研究结果.在第二章,第三章和第四章中,我们均使用反证法,通过构造极小反例,运用势函数以及权转移方法,分别证明了以下三个结果:(1)围长g≥5的平面图存在(Fd1,Fd2)-分解,其中{d1,d2}∈{{4,4},{3,5},{2,6}}.(2)围长g≥6的平面图存在(F1,F4)-分解.(3)对于k≥2,若图G满足mad(G)≤2+k/(k+1),则G存在(I,Fk)-分解.需要指出,结论(1)中的三个结果分别改进了文献[10,24,31]中的三个已知结果.结论(2)和结论(3)改进了发表在Journal of Combinatorial Theory,Series B上的两个结果.另外,由于存在围长为6且不具有(I,?d)-分解的平面图例子,结论(2)中的F1是最优的.