Anti-Ramsey问题中的极图与相关问题研究

The anti-Ramsey theory concerns the maximum number of colors in an edge-colored graph which contains no rainbow given subgraphs. This theory is a colored version of Turán type problems that concern the maximum number of edges in a graph which contains no given subgraphs. In the research of extremal type problems, the structure of extremal graphs is one of the key points that scholars are very interested in. Extremal graphs of many Turán type problems had been settled, but there were only few results about the extremal graphs of anti-Ramsey type problems. For this reason, this project will study the extremal graphs of cliques and matchings in their anti-Ramsey type problems, i.e. the structure of the edge-colored graphs which contain no rainbow given subgraphs and have the maximum number of colors. Moreover, this project will study the structure of those edge-colorings (not necessarily with maximum number of colors) which contain no rainbow given subgraphs, and monochromatic subgraphs in such colorings (Gallai-Ramsey problems). By concerning extremal graphs in anti-Ramsey theory, and trying to use methods and tools in the research of Turán type problems and Gallai-Ramsey theory, this project is expected to get some profound results.

Anti-Ramsey问题研究的是图的边着色中不含彩虹的给定子图时颜色数的最大值。这一问题可以看成是着色版本的Turán型问题，后者研究的是图中不含给定子图时边数的最大值。在极值型问题的研究中，取到极值的极图往往是研究者们关注的一个重点。关于Turán型问题的极图目前已有较多的结果，而关于anti-Ramsey问题极图的结果却还很少。基于这个原因，本项目首先将研究团和匹配的anti-Ramsey问题中的极图，也即不含相应彩虹子图且颜色数达到最大的边着色图的结构。进一步，本项目将研究边着色图中不含相应彩虹子图时着色的结构（颜色数不一定最大），以及这些着色中单色子图的存在性问题（Gallai-Ramsey问题）。本项目将围绕anti-Ramsey问题中的极图，结合Turán型问题与Gallai-Ramsey问题研究中的方法和工具进行研究，期望得到一些深刻的结果。

Anti-Ramsey型问题以及相关问题主要研究图中不含特定着色子图时图中颜色数的极值. 本项目希望研究一些相关极值问题中的极图, 得到关于极图结构的刻画. 在项目执行期间, 我们围绕一般图中彩虹三角形, 正常着色4-圈以及完全图中的单色匹配得到了以下结果：一、研究了一般图中存在彩虹三角形的超饱和问题并刻画了相应的极图. 二、证明了一般图中关于边数加色数条件下正常着色子图的存在性定理可推导出相应色度和条件版本的定理. 确定了一般图中存在正常着色4-圈的边数加色数条件的极值, 并刻画了极图的结构. 三、运用关于最大匹配的Gallai-Edmonds结构定理刻画了匹配Ramsey数极图的结构. 该结论给出了匹配Ramsey数的一个新证明.