相邻顶点度和至多为8的二部图的强边染色  

Strong Edge Colorings on Bipartite Graphs with Degree Sum of Adjacent Vertices at Most 8

作　　者：闫训祥 

机构地区：[1]山东师范大学数学与统计学院,山东济南

出　　处：《应用数学进展》2019年第7期1224-1227,共4页Advances in Applied Mathematics

摘　　要：二部图G指顶点集V(G)可以划分成两个不相交的子集,使得在同一个子集内的顶点不相邻的图。图G的强边染色是在正常边染色的基础上,要求长至多为3的路上的边染不同的颜色。我们证明了每一对相邻顶点度和至多为8的二部图有一个强边染色至多22种颜色。A bipartite graph G is a graph in which V(G)can be partitioned into two disjoint subsets,so that the vertices in the same subset are not adjacent.A strong edge coloring of graph G is an edge coloring in such a way that any two edges on a path of length at most three receive distinct colors.We prove that each bipartite graph with degree sum of each pair of adjacent vertices at most 8 has a strong edge coloring with at most 22 colors.

关 键 词：二部图 强边染色 度和 

分 类 号：O1[理学—数学]