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

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

摘要: 二部图G指顶点集V(G)可以划分成两个不相交的子集，使得在同一个子集内的顶点不相邻的图。图G的强边染色是在正常边染色的基础上，要求长至多为3的路上的边染不同的颜色。我们证明了每一对相邻顶点度和至多为8的二部图有一个强边染色至多22种颜色。

Abstract: 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.