| Title:
|
Proper connection number of bipartite graphs (English) |
| Author:
|
Yue, Jun |
| Author:
|
Wei, Meiqin |
| Author:
|
Zhao, Yan |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
68 |
| Issue:
|
2 |
| Year:
|
2018 |
| Pages:
|
307-322 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
proper coloring |
| Keyword:
|
proper connection number |
| Keyword:
|
bipartite graph |
| Keyword:
|
dominating set |
| MSC:
|
05C15 |
| MSC:
|
05C69 |
| MSC:
|
05C75 |
| idZBL:
|
Zbl 06890375 |
| idMR:
|
MR3819176 |
| DOI:
|
10.21136/CMJ.2018.0122-16 |
| . |
| Date available:
|
2018-06-11T10:50:56Z |
| Last updated:
|
2020-07-06 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/147221 |
| . |
| Reference:
|
[1] Andrews, E., Lumduanhom, C., Laforge, E., Zhang, P.: On proper-path colorings in graphs.J. Comb. Math. Comb. Comput. 97 (2016), 189-207. Zbl 1347.05055, MR 3524734 |
| Reference:
|
[2] Bondy, J. A., Murty, U. S. R.: Graph Theory.Graduate Texts in Mathematics 244, Springer, New York (2008). Zbl 1134.05001, MR 2368647, 10.1007/978-1-84628-970-5 |
| Reference:
|
[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. Zbl 1246.05090, MR 2935404, 10.1016/j.disc.2011.09.003 |
| Reference:
|
[4] Li, X., Magnant, C.: Properly colored notations of connectivity---a dynamic survey.Theory and Applications of Graphs 0 (2015), Article 2, 30 pages. MR 2606615, 10.20429/tag.2015.000102 |
| Reference:
|
[5] Li, X., Shi, Y., Sun, Y.: Rainbow connections of graphs: a survey.Graphs Comb. 29 (2013), 1-38. Zbl 1258.05058, MR 3015944, 10.1007/s00373-012-1243-2 |
| Reference:
|
[6] Li, X., Sun, Y.: Rainbow Connections of Graphs.Springer Briefs in Mathematics, Springer, New York (2012). Zbl 1250.05066, MR 3183989, 10.1007/978-1-4614-3119-0 |
| Reference:
|
[7] Li, X., Wei, M., Yue, J.: Proper connection number and connected dominating sets.Theor. Comput. Sci. 607 (2015), 480-487. Zbl 1333.05227, MR 3429068, 10.1016/j.tcs.2015.06.006 |
| . |
