与Steinberg猜想、全染色猜想相关的若干问题

We mainly study such two problems: .(1) Is I empty? where I is the set of integers i>4, if any, such that every planar graph with neither 4-cycle nor i-cycle is 3-colorable..(2) Total colorability of planar graphs with maximum degree plus one..The former is related to the longstanding Steinberg's conjecture which asserts that 5 belongs to I; the later concerns that whether the Total Coloring Conjecture （Every simple graph is totally colorable with maximum degree plus two colors）is hold for planar graphs; and that which planar graphs are totally colorable with maximum degree plus one colors.. Moreover, we study some other related problems in terms of list colorings and improper colorings, they both are natural (but different in nature) generalizations of the classical proper colorings, and have been extensively studied. The further study of them may extend the space for study of those lonstanding conjectures on classical proper colorings.. Based on previous results in the literature, we mainly analyze the structures of counterexamples to the problems under consideration in larger scale and more profund level; try to yield some new ideas or tequniques on analysis of integration of combinatorial structures as well as on discharging methods.. More than 20 papers published in SCI source journals are promised in forthcoming 4 years.

主要研究两个问题：（1）使得既没有4-圈又没有i-圈的平面图是3可染的正整数i>4所形成的集合I是否为空集？（2）可平面图的最大度加1的全可染性。前一问题与长期悬而未决的Steinberg猜想"5属于I"有关；后一问题考虑全染色猜想（每个简单图是最大度加2全可染的）在平面图类内是否成立及比猜想更强的结论是否成立的问题。此外还研究相关的列表染色、非正常染色等问题。列表染色和非正常染色是通常正常染色在两种不同意义下的自然而又更为普遍的推广， 已得到广泛研究。对它们的深入研究，可为研究尚未解决的有关正常染色的猜想提供更广阔的视野和研究空间。主要在前人研究的基础上, 对问题的极小反例，进行大范围的更深刻的结构分析，力求在结构组合的分析技巧系统化方面和权转移方法上推陈出新。计划4年内在SCI源期刊上发表学术论文20余篇。

围绕图染色理论中两个著名猜想，即Steinberg猜想和全染色猜想，展开研究。. . Steinberg于1976年猜想：没有4-圈和5-圈的平面图是3色可染的。全染色猜想为Vizing（1964）和Behzad（1965）相互独立提出：每个简单图是最大度加2全可染的。这两个猜想被Bondy和Murty列为当今图论中100个尚未解决的重要问题中的第53个和第61个问题。前者还在Open Problem Garden 中被列为6个4星级（最高级）问题之一。后者后来引申出许多著名的新猜想，如列表全染色猜想，完备染色猜想等。. . 本项目提出并研究比Steinberg猜想更为一般的一个问题，可称之为Post Steinberg Problem, 缩写为PSP, 即使得没有4-圈和i-圈（i>4)的平面图是3色可染的正整数i所形成的集合I是什么？最近，Steinberg猜想已被Cohen-Addad等人所否定，这表明PSP是一个具有深远影响且极具挑战性的问题。由于已经知道没有4-，i-，j-, k-圈（4<i<j<k<10)的平面图是3色可染的, 因此，系统研究没有4-，i-，j-圈的平面图的3染色问题及没有4-，k-圈，或没有单个k-圈的平面图的非正常3染色问题对于研究PSP具有积极的意义。. 图的非正常3染色是图的正常3染色的一个自然推广：设d1, d2, d3 是三个非负整数。若图G 的顶点集能剖分成三个子集，使得第i个子集所导出的子图的最大度不超过di, 则称图G是(d1,d2,d3)-可染的。于是Steinberg猜想可改述为：没有4-，5-圈的平面图是(0,0,0)-可染的. 围绕PSP，本项目证明了以下结果：.没有4-圈的平面图是列表(1,1,1)-可染的. .没有5-圈的平面图是(1,1,1)-可染的..对于i=5,6,7, 没有4-，i-圈的平面图是(3,0,0)-，(1,1,0)-, (2,0,0)-可染的..没有4-，8-圈, 或没有相邻的长度不超过5的圈的平面图是(1,1,0)-可染的. .没有4-，i-, j-圈(4<i<j<10)的平面图是(1,0,0)-可染的..没有4-，6-, 9-圈，或没有4-，5-圈且没有(k, 7)-弦(k=3,5,7)，或长度不超过5的圈的距离不小于2的平面图是(0,0,0)-