图的瑕疵染色与群连通度的若干问题

The coloring of graphs is an important researching contents of graph theory, and it has been widely applied to the computer science, information science, so a good deal of attention to it is still paid by numerous academics in graph theory in and abroad. It is well known that the problem of deciding whether a planar graph is properly 3-colorable is NP-complete. The defective colorings of planar graphs is one of the important research themes in this field. And the concept of integer flow is introduced by Tutte trying to attack the famous four colors conjecture, and again, it is successfully generalized by Jaeger et al. to group connectivity. Motivated by Bordeaux Conjecture and Jaeger's Z_3-connected Conjecture, we plan to, in this project, be interested to some interesting problems related with the research of the defective coloring of planar graphs and group connectivity of gaphs, including:(1) planar graphs without 3-cycles adjacent to cycles of length 3 or i are (1,1,1)-colorable, where i is a positive integer but not 5, and 3<i<10;(2) planar graphs with neither intersecting triangles nor 5-cycles are (1,0,0)-colorable;(3) by two forbidden subgraphs, character these graphs which are Z_3-connected in a family of 2-connected graphs containing no such forbidden subgraphs;(4) by the structured approach of graphs, study a problem that a given graphical sequence D has a realization that is strongly Z_(2s+1)-connected.

图的染色是图论中一个重要的研究内容，它在计算机科学、信息科学等领域有着十分广泛的应用，一直受到国内外众多图论学者的极大关注。众所周知，平面图的3-色问题是一个NP-complete问题。平面图的瑕疵染色是其重要研究主题之一。整数流是Tutte在尝试攻克四色猜想时引入的，而Jaeger等又把整数流扩展到群连通。在Bordeaux猜想和Jaeger的Z_3-连通猜想的激励下，本项目拟对平面图的瑕疵染色及图的群连通度中一些有意义的问题展开研究，其中内容包括：(1)不含3-圈与3-、i-圈相邻的平面图是(1,1,1)-可染，其中i为不等于5的正整数并且3<i<10；(2)不含5-圈及相交三角形的平面图是(1,0,0)-可染；(3)利用两个禁用子图，在不含这两个禁用子图的2-连通图中刻画出Z_3-连通的图；(4)利用构造法研究给定图的度序列D有强Z_(2s+1)-连通实现问题。

本项目计划主要研究图理论中的两类典型问题：平面图的非正常染色及图的群连通性相关问题。首先，我们重点研究了不含三角形与短圈相邻的平面图的(1,1,1)-可染问题，通过超延拓与权转移方法证明了两个结论：不含三角形与4-圈相邻的平面图是(1,1,1)-可染的，不含三角形与三角形及6-圈相邻的平面图是(1,1,1)-可染的。其次，我们研究了Novosibirsk猜想的一个松弛问题。该猜想陈述不含有三角形与三角形及5-圈皆相邻的平面图是3-色可染的。由于Steinberg猜想被证明是错误的，这意味着不是每个不含4-,5-圈的平面图是3-可染的。从而，Novosibirsk猜想所考虑的平面图并不是每个可以3-可染的。自然地，我们提问，每个不含三角形与三角形及5-圈皆相邻的平面图是否(1,0,0)-可染呢？在该问题激励下，我们证明了每个不含三角形与3-圈及5-圈皆相邻的平面图是(1,1,0)-可染的。再是，研究刻画禁对子图使得一个连通图的边连通度与其最小度相等的充分必要条件。我们希望利用该方法来研究图的群连通性相关问题。此外，项目组证明了不含三角形相邻于两个5-圈的平面图是DP-4-可染的，以及证明了边权重至多6的图的强边色数至多为10，边权重至多6的图的强边色数至多为15。通过本项目研究，项目所取得的结论提高或加强了前人的多个结论，使本领域的相关结论得到一定的丰富与发展。