图的顶点划分及其相关问题的研究

A partition of a graph G is a decomposition of V(G) into subsets V1, V2,…, Vm such that V(G)=V1∪V2∪…∪Vm and Vi∩Vj=?. The problem of the graph partition has been widely used in the field of computer, and has been one of the heat problems in graph theory research. This problem contains many improtant problems in graph theory, for example, the classic coloring of graphs, the famous max-cut problem, the factor decomposition problem, etc. The vertex arboricity va(G) of graph G is defined as the minimum of subsets in a partition of the vertex set of G so that each subset induces an acyclic subgraph and has been widely studied. The research on the vertex arboricity of a graph is an improtant research direction in the graph partition field, and its progress plays an great role on the research of the problem of graph coloring. This project mainly puts emphasis on the theory of vertex arboricity of graphs and other several kinds of problems in graph partition, makes every effort on the conjecture of the vertex arboricity of graphs without adjacent triangles to have the new progress, some kinds of graphs with same vertex arboricity and circular vertex arboricity should be disscussed also, some results about the coloring of graphs also should be got used the conclusions made above.

图的划分问题是指把图的顶点集或边集划分成一些互不相交的子集的并，使得划分之后的子集（边子集）或子集之间（边子集之间）满足某些条件。图的划分问题在计算机领域有着广泛应用，并一直是图论研究的热点问题之一，它包含许多图论中的重要问题，例如经典的着色问题，著名的最大割问题，因子分解问题等等。无向图的顶点荫度，也称点荫度，是将图的顶点集划分为若干互不相交的顶点子集，使每个顶点子集的导出子图是森林的最小的整数，对图的点荫度的研究是图的划分中的重要研究方向，对于图的染色问题的解决起着很大的作用。本项目主要研究图的顶点荫度，及其它几种形式的图的顶点划分问题，力求解决图的无相邻三角形顶点荫度猜想，研究图的圈顶点荫度与图的顶点荫度相同的一些图类，同时研究结果应用于图的染色，给出图的染色的一些结果。

项目组成员在本课题中计划研究图的顶点荫度，2013年间我们基本按原计划执行，并且取得一些相关结果和进展。即系统研究了轮胎图的无圈顶点荫度和列表顶点荫度，证明了每个无4圈轮胎图的顶点荫度是2，并将此结构性理论运用于图的染色，即每个无4圈的轮胎图是4可着色的。此外，项目组负责人张海辉还研究了图的列表顶点荫度，证明了无5圈轮胎图的列表荫度为2，无6圈和7圈及相邻三圈的轮胎图的列表荫度亦为2。这些结论解决了Raspaud和王维凡提出的的关于图的顶点荫度的一个类似问题，即保证每个没有k-圈的轮胎图的顶点荫度是2的最大的整数k是5。. 张海辉还研究了图的正常的染色，即划分为若干个导出子图为独立集的图的划分，给出了无指定构型的一些图的三选色的充分条件，并研究了图的线性荫度，图的线性荫度是图的边集的一个分解，使得每个边子集导出子图为线性森林的最小的划分数。张海辉证明了每个无相邻三角形的轮胎图满足线性荫度猜想。. 项目主持人张海辉在2013年间发表标注基金资助号的论文3篇，其中1篇发表在EI期刊上。另有3篇标注基金号的期刊杂志论文正在审稿阶段。. 项目组成员唐娜通过研究超可解群和p-超可解群的结构，给出了此两类群的相应的充分必要条件。2013年她的2篇标注基金资助的相关论文分别发表在扬州大学及吉林大学学报上。项目组成员梁华2013年在数学的实践与认识上发表论文一篇。. 尽管项目组成员在轮胎图的顶点荫度与列表顶点荫度研究方面取得一些进展，但由于时间有限，在研究图的圈顶点荫度中遇到困难，没有什么进展，同时也是受时间所限，未能得出相应结果，未能突破相邻三角形的2荫度的猜想，需要发明新的方法工具来进一步研究该问题。