Proper connection number of bipartite graphs
Proper connection number of bipartite graphs
复制标题
二分图的正确连接数
DOI：
10.21136/cmj.2018.0122-16
复制
发表时间：
2018
影响因子：
0.5
通讯作者：
Zhao Yan
中科院分区：
文献类型：
--
作者：
Yue Jun;Wei Meiqin;Zhao Yan
一个边色图G是真连通的，如果每一对顶点都有一条真路连接。连通图G的真连通数，记为PC(G)，是为图G的边着色以使其真连通所需的最小颜色数。本文得到了一般二部图G和一系列极值图的PC(G)的精确上界。此外，我们还给出了连通二部图G具有δ(G)≥2和控制圈或控制完全二部子图PC(G)=2的真2-染色，并得到了具有δ≥2和Diam(G)≤4的连通二部图的真连通数为2。
An edge-colored graph G is proper connected if every pair of vertices is connected by a proper path. The proper connection number of a connected graph G, denoted by pc(G), is the smallest number of colors that are needed to color the edges of G in order to make it proper connected. In this paper, we obtain the sharp upper bound for pc(G) of a general bipartite graph G and a series of extremal graphs. Additionally, we give a proper 2-coloring for a connected bipartite graph G having δ(G) ≥ 2 and a dominating cycle or a dominating complete bipartite subgraph, which implies pc(G) = 2. Furthermore, we get that the proper connection number of connected bipartite graphs with δ ≥ 2 and diam(G) ≤ 4 is two.