关于Steinberg猜想及其相关问题的研究

The theory of graph coloring is one of the popular fields that most scholors are interested in. It has more applications in all kinds of subjects such as in Chanal Assignment, Coding theory and in Large scale integration. To determine which class of planar graphs are 3 colorable is one of the important content in the study of planar graph coloring. The central task of this project is around the Steinberg's conjecture, we shall study the problems on planar graph colorings, vertex-chromatic-critical graphs, independence numbers of planar graphs and planar Ramsey numbers etc. We will study the graphs that satisfy the condition of the Steinberg's Conjecture, hoping that we can know much about the structural properties of planar graphs which contain neither 4 cycles nor 5 cycles. Then we can use these properties and our relaxation methods to evaluate the Steinberg's Conjecture. We hope to publish 10 to 12 papers, among which at least 8 papers are published in high standard Journals during this project.

图染色理论一直是组合学和图论研究的热点之一，它在频道分配、编码、大规模集成电路设计等领域有广泛应用。确定平面图中哪些图类是3色的是平面图染色的重要内容之一。本项目主要围绕Steinberg猜想对平面图的着色、临界图、独立数、平面Ramsey数等问题进行研究。我们首先针对Steinberg猜想的条件所涉及的相关图类进行一般性的研究，希望尽可能弄清楚不含4圈以及5圈的平面图所具有的结构及其性质，然后利用这些性质以及我们提出的松弛方案来探讨Steinberg猜想。本项目拟在四年内完成学术论文 10-12 篇, 其中 8 篇左右发表在 SCI 刊物上。

图染色理论一直是组合学和图论研究的热点之一，它在频道分配、编码、大规模集成电路 设计等领域有广泛应用。确定平面图中哪些图类是3色的是平面图染色的重要内容之一。本项目主要围绕Steinberg猜想对平面图的着色、临界图、独立数、平面Ramsey数等问题进行研究 。我们首先针对Steinberg猜想的条件所涉及的相关图类进行一般性的研究，希望尽可能弄清楚不含4圈以及5圈的平面图所具有的结构及其性质，然后利用这些性质以及我们提出的松弛方案来探讨Steinberg猜想。.在本项目的资助下，我们给出给出了几个新的构造4临界图的新方法，这些方法异于经典的Hajos的构造方法；确定了不含某些禁用子图的4临界平面图的最大边数等（详情参见正文）。本项目共整理成10篇论文，其中7篇已发表，3篇处于投稿状态中。