Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
proper coloring; proper connection number; bipartite graph; dominating set
proper coloring; proper connection number; bipartite graph; dominating set
Summary:
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)\geq 2$ 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 \geq 2$ and ${\rm diam}(G)\leq 4$ is two.
References:
[1] Andrews, E., Lumduanhom, C., Laforge, E., Zhang, P.: On proper-path colorings in graphs. J. Comb. Math. Comb. Comput. 97 (2016), 189-207. MR 3524734 | Zbl 1347.05055
[2] Bondy, J. A., Murty, U. S. R.: 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] Borozan, V., Fujita, S., Gerek, A., Magnant, C., Manoussakis, Y., Montero, L., Tuza, Z.: Proper connection of graphs. Discrete Math. 312 (2012), 2550-2560. DOI 10.1016/j.disc.2011.09.003 | MR 2935404 | Zbl 1246.05090
[4] Li, X., Magnant, C.: 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 | MR 2606615
[5] Li, X., Shi, Y., Sun, Y.: 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] Li, X., Sun, Y.: 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] Li, X., Wei, M., Yue, J.: 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
Search
Partner of
