两类与嵌入树相关的猜想的研究

Tree is a very important concept in graph theory. There are many applications on trees such as Decision Theory, Artificial Intelligence, Machine Learning and so on. Tree embedding problem is a branch of graph theory with very strong theoretical property. It's study has an important significance to extremal graph theory and structure graph theory. In this project, we discuss the following two classes of conjectures and problems with respect to embedding trees. (1) Erdős-Sós conjecture which says if a graph G has more than (k-1)n/2 edges then G contains every tree with k edges. We start with some special classes of trees and characterize the case that they can be embedded into some place around any given vertex of G. Then combining with algebra and randomization methods, try to make a process on the sulotion of the problem. (2) Akiyama-Watanable conjecture that says any bipartite planar graph has an induced forest of order at least 5n/8. We try to start to improve the known lower bound. Combining with Euler formula and weight transformation methods, we may deduce some special structure of G. Then deal with every deduced cases by reduction and try to make a process on the solution of the problem. The above two embedding tree problems are important problems in graph theory. Their studying will make further progress on other graph theory problems, such as packing problem, feedback vertex set problem, and so on.

树是图论中非常重要的概念，在决策论、人工智能、机器学习等方面有着非常广泛的应用。树嵌入问题是图论中理论性较强的一部分，其研究对极值图论与结构图论都有重要意义。本项目围绕以下两类与嵌入树相关的问题展开研究：(1) Erdős-Sós猜想：如果图G的边数超过(k-1)n/2则任意k条边的树都可以嵌入到图G中。项目计划从一些特殊树类出发，刻画它们可以嵌入到图G中的指定的位置的情形，然后结合代数，概率等手段争取对相关问题有所推动。(2) Akiyama-Watanable猜想：任意平面二部图包含至少有5n/8个点的导出森林。项目计划从改进目前已知的下界出发，利用欧拉公式，结合权转移方法可以导出一些特殊的局部结构，然后针对每种结构进行约化，争取推进相关问题的解决。以上两类嵌入树问题为图论中的十分重要的问题，其研究对图论中许多其他问题，比如填装问题、反馈集问题等，都有十分重要推进作用。

树是图论中非常重要的概念，在许多方面有着非常广泛的应用。树嵌入问题是图论中理论性较强的一部分，其研究对极值图论与结构图论都有重要意义。本项目围绕Erdős-Sós猜想和Akiyama-Watanable猜想等两类嵌入树相关的问题展开研究，主要研究了以下问题：(1)Erdős-Sós猜想:任意平均度超过k-1的图G包含任意k条边的树，我们主要证明了猜想对spider和comb树的情况；(2)Akiyama-Watanable猜想：任意点数为n的无三角平面图包含一个点数至少为5n/8的导出森林。我们研究无三角平面图上最大导出森林和最大导出线性森林，改进了Dross等人的所给出的下界，并且还解决了Dross等人提的一个猜想；(3)对路分解、划分和染色问题。主要是研究了Gallai路分解猜想，证明了最大度不超过6且6度点构造独立集的图可分解成(n+1)/2条路，对3正则图证明了存在一棵支撑树T使得G-E(T)是一些点不相交的长度不超过2的路，同时对claw-free的3正则图，证明了3划分猜想成立；此外，还研究了染色问题，证明了ISK4-free图总是可以8染色的，同时对{ISK4, bowtie, diamond}-free图证明了Léveque, Maffray 和Trotignon的猜想成立; (4)可去子图问题：提出了嵌入树存在的全新的充分条件，并且利用此条件给出了从已知的嵌入树中替换一个点的充分必要条件。进一步，我们研究了Mader猜想：对任意m个点的树T以及对任意最小度至少为3k/2+m-1的k-连通图G都包含一个子树同构于T且满足G-V(T)是k-连通图。我们证明了Mader猜想当k=2时对spider和caterpillar成立。该结论几乎包含了当前已知的Mader猜想对k=2时的结论；然后利用替换树的充分条件，给出了对任意树的通用嵌入方法，从而证明了Mader猜想当k=2和3时对任意树都成立。.通过以上与嵌入树相关的若干猜想和问题的研究，推动了相关猜想的进展，共计在Journal of Graph Theory, Discrete Mathematics和Discrete Applied Mathematics等国际著名SCI杂志发表学术论文11篇。