Czechoslovak Mathematical Journal, first online, pp. 1-16

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
Classification MSC:  05C15, 05C69, 05C75
DOI:  10.21136/CMJ.2018.0122-16

PDF available at:  Institute of Mathematics CAS

[1] E. Andrews, C. Lumduanhom, E. Laforge, P. Zhang: On proper-path colorings in graphs. J. Comb. Math. Comb. Comput. 97 (2016), 189-207. MR 3524734 | Zbl 1347.05055
[2] J. A. Bondy, U. S. R. Murty: Graph Theory. Graduate Texts in Mathematics 244, Springer, New York (2008). DOI 10.1007/978-1-84628-970-5 | MR 2368647 | Zbl 1134.05001
[3] V. Borozan, S. Fujita, A. Gerek, C. Magnant, Y. Manoussakis, L. Montero, Z. Tuza: Proper connection of graphs. Discrete Math. 312 (2012), 2550-2560. DOI 10.1016/j.disc.2011.09.003 | MR 2935404 | Zbl 1246.05090
[4] X. Li, C. Magnant: Properly colored notations of connectivity - a dynamic survey. Theory and Applications of Graphs 0 (2015), Article 2, 30 pages. DOI 10.20429/tag.2015.000102
[5] X. Li, Y. Shi, Y. Sun: Rainbow connections of graphs: a survey. Graphs Comb. 29 (2013), 1-38. DOI 10.1007/s00373-012-1243-2 | MR 3015944 | Zbl 1258.05058
[6] X. Li, Y. Sun: Rainbow Connections of Graphs. Springer Briefs in Mathematics, Springer, New York (2012). DOI 10.1007/978-1-4614-3119-0 | MR 3183989 | Zbl 1250.05066
[7] X. Li, M. Wei, J. Yue: Proper connection number and connected dominating sets. Theor. Comput. Sci. 607 (2015), 480-487. DOI 10.1016/j.tcs.2015.06.006 | MR 3429068 | Zbl 1333.05227

Affiliations:   Jun Yue, School of Mathematic and Statistics, Shandong Normal University, 88 Wenhua E Road, Jinan 250014, Shandong, China, e-mail:; Meiqin Wei, College of Arts and Sciences, Shanghai Maritime University, 1550 Haigang Ave, Shanghai 201306, China, e-mail:; Yan Zhao, Department of Mathematics, Taizhou University, Wangtiantai, Taizhou 225300, Jiangsu, China, e-mail:

PDF available at: