图的点区别边染色和全染色

Graph coloring is an important branch of graph theory, which has wide applications in practical problems. In this project, starting with the structural properties of graphs, we discuss the adjacent vertex-distinguishing edge (total) coloring, the adjacent sum-distinguishing edge (total) coloring, and the distance 2 vertex-distinguishing edge (total) coloring. The research aims at several open problems in related areas and makes use of combinatorial, algebraic, probabilistic, discharging and edge-partition methods. We try to show the following results: (1) The adjacent vertex-distinguishing chromatic index of a normal graph is at most 2Δ, and a planar graph with Δ≥13 has the adjacent vertex-distinguishing chromatic index Δ+1 if and only if it contains adjacent Δ-vertices. (2) The adjacent vertex-distinguishing total chromatic number of a graph is at most ⌈3Δ/2⌉, and a planar graph with Δ≥11 has the adjacent vertex-distinguishing total chromatic number Δ+2 if and only if it contains adjacent Δ-vertices. (3) There exists a constant c such that the distance 2 vertex-distinguishing chromatic index of every graph is bounded by cΔ. At least 20 papers are published after the project is finished, at least 10 of which are indexed by SCI.

图的染色是图论研究的重要内容，在实际问题中有广泛应用。本项目从图的结构性质入手，研究图的邻点区别边染色和全染色、邻和区别边染色和全染色、距离2点区别边染色和全染色等问题。围绕着本领域的几个公开问题，借助组合、代数、概率、权转移、边分解、算法分析等方法，对上述参数进行刻画或给出好的上界。在图的邻点区别边染色方面，证明每个正常图的点区别边色数至多是2Δ，及Δ≥13的平面图有邻点区别边色数Δ+1当且仅当它有两个相邻的最大度点；在图的邻点区别全染色方面，证明每个图的邻点区别全色数至多是⌈3Δ/2⌉，及Δ≥11的平面图有邻点区别全色数Δ+2当且仅当它有两个相邻的最大度点；在图的距离2点区别边染色方面，证明存在一个常数c使得每个图的距离2点区别边色数至多是cΔ。拟在四年内完成学术论文20余篇，其中10篇以上发表在SCI杂志上。

图的染色一直图论研究的重要内容,在现代计算机科学、信息科学、管理科学等领域有着十分广泛的应用。本项目从图的结构性质入手，研究图的各种染色问题，包括图的邻点区别边染色和全染色、强边染色和星边染色、无圈点染色和边染色、平面图的完备染色和边面染色、图的点荫度和线性荫度等内容,得到一些有意义的研究成果。刻画了最大度至少为14的平面图的邻点区别边色数和最大度至少为11的平面图的邻点区别全色数;引入和研究了图的距离2点区别的边(全)染色和严格邻点区别边(全)染色;证明了1-平面图是18-无圈点可染的,IC-平面图是无圈10-点可染的,所有1-平面图是(Δ+36)-无圈边可染的;证明了1-平面图的强边色数至多为14Δ;给出平面图星边色数2.75Δ+18的上界;证明了Δ≥20的2-连通平面图的完备色数为Δ+1;证明了Δ≥7的平面图是(Δ+1)-边面可染的;证明了环面图的列表点荫度至多为4,且为4当且仅当K7作为一个子图。此外考虑了图的列表染色和对角染色、整数流、化学指标等问题。立项以来,项目组成员在国内外学术刊物上发表论文59篇,其中被 SCI 检索46篇, 获教育部自然科学学术奖二等奖1项。