Czechoslovak Mathematical Journal, Vol. 68, No. 2, pp. 307-322, 2018
Proper connection number of bipartite graphs
Jun Yue, Meiqin Wei, Yan Zhao
Received March 13, 2016. First published February 8, 2018.
Abstract: 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 ${\rm 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 ${\rm 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 $\delta(G)\geq2$ and a dominating cycle or a dominating complete bipartite subgraph, which implies ${\rm pc}(G)=2$. Furthermore, we get that the proper connection number of connected bipartite graphs with $\delta\geq2$ and ${\rm diam}(G)\leq4$ is two.
Keywords: proper coloring; proper connection number; bipartite graph; dominating set
Affiliations: Jun Yue, School of Mathematic and Statistics, Shandong Normal University, 88 Wenhua E Road, Jinan 250014, Shandong, China, e-mail: yuejun06@126.com; Meiqin Wei, College of Arts and Sciences, Shanghai Maritime University, 1550 Haigang Ave, Shanghai 201306, China, e-mail: weimeiqin8912@163.com; Yan Zhao, Department of Mathematics, Taizhou University, Wangtiantai, Taizhou 225300, Jiangsu, China, e-mail: zhaoyan81.2008@163.com