图同态中的极值问题

Graph homomorphism is one of the most useful tools in graph theory. Some parameters such as coloring,fractional coloring and nowhere-zero flow are in some kinds of equivalent relationship with graph homomorphism. In 2007 Naserasr conjectured that for any given integer k>0, every planar graph of odd-girth at least 2k+1 admits a homomorphism to PC(2k). Guenin generalized this conjecture to signed graph: Given an integer k>1, very planar consistent signed graph of unbalanced-girth k+1 admits a homomorphism to SPC(k). These two conjectures are both the extensions of Four-Colour Theorem. Moreover, they are proved to be equivalent to Seymour’s conjecture on edge-coloring of r-graphs. In this project, we will focus on some related problems on homomorphism of planar graphs and signed graphs.On Naserasr’s conjecture, we will work on the existence of homomorphism of planar graphs with given odd-girth to the sub-graphs of the projective cubes and the minimum order of these sub-graphs. Regarding to Guenin’s conjecture, we will work on the existence and minimality of homomorphism of planar bipartite signed graphs to the sub-graphs of the singed projective cubes.

图的同态是研究图论中许多参数的重要工具之一。许多参数，如图的染色、分数染色、非零流等都与图的同态存在某种等价关系。2007年,Naserasr猜想：给定整数k>0，任何奇围长至少是2k+1的平面图都可以同态映射到投影立方体PC(2k)。Guenin将Naserasr猜想推广到了标号图上：给定整数k>1，任何非平衡围长至少是k+1的一致标号平面图都可以同态映射到标号投影立方体SPC(k)。这两个猜想都是四色定理的推广，同时也被证明了与Seymour著名的r-图的边染色猜想等价。本项目旨在研究这两个猜想相关的图的同态和标号图的同态问题。一方面，围绕Naserasr的猜想，研究给定奇围长的平面图到投影立方体子图同态映射的存在性问题，以及同态映射目标图点数最小性问题。另一方面，围绕Guenin的猜想，研究标号二部平面图到标号投影立方体子图同态映射的存在性以及最小性问题。

四色猜想（定理）是图论中最重要的课题之一，对四色猜想的研究极大地促进了图论的发展，引出了图的点染色，边染色，图的同态，DP染色，整数流等许多重要的课题。1953年，Harary为了解决一系列社会性问题，创造性地引入了符号图，用正号表示友好关系，符号表示敌对关系。自此之后，符号图中的染色问题，同态问题，整数流问题等越来越多地引起众多学者的兴趣，成果丰富，很多相关的问题也有待解决。.依托本项目，我们主要研究了平面图的DP染色问题，符号广义Pestersen图的边色数问题，符号广义Mycielski图的边色数问题，符号Halin图的变色问题以及相关问题的一些应用。在平面图的DP染色问题方面，我们证明了任何不含长度是4,5,7圈的平面图都是DP-(3,1)*可染色的；任何不含长度是4,5,9圈的平面图都是DP-(3,1)*可染色的；任何不含长度是4,8圈的平面图都是DP-(3,1)*可染色的。在符号图的边色数方面，我们证明了几乎所有的符号广义Petersen图P(n,1), P(5,2),P(6,2)的边色数是3，同时给出了一些是等于4的例子。对于符号广义Mycielski图，我们证明了原图边色数等于最大度的时候，其对应的符号广义Mycielski图的边色数也等于最大度。对于符号Halin图，我们证明了其边色数等于最大度。. 在本课题的资助下，已在国际期刊发表SCI论文4篇，培养了3名研究生。