Geodesic
Proper connection number of bipartite graphs
Czechoslovak Mathematical Journal, Tome 68 (2018) no. 2, pp. 307-322 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.21136/CMJ.2018.0122-16
Classification : 05C15, 05C69, 05C75
Keywords: proper coloring; proper connection number; bipartite graph; dominating set 
@article{10_21136_CMJ_2018_0122_16,
     author = {Yue, Jun and Wei, Meiqin and Zhao, Yan},
     title = {Proper connection number of bipartite graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {307--322},
     year = {2018},
     volume = {68},
     number = {2},
     doi = {10.21136/CMJ.2018.0122-16},
     mrnumber = {3819176},
     zbl = {06890375},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2018.0122-16/}
}
TY  - JOUR
AU  - Yue, Jun
AU  - Wei, Meiqin
AU  - Zhao, Yan
TI  - Proper connection number of bipartite graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2018
SP  - 307
EP  - 322
VL  - 68
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2018.0122-16/
DO  - 10.21136/CMJ.2018.0122-16
LA  - en
ID  - 10_21136_CMJ_2018_0122_16
ER  - 
%0 Journal Article
%A Yue, Jun
%A Wei, Meiqin
%A Zhao, Yan
%T Proper connection number of bipartite graphs
%J Czechoslovak Mathematical Journal
%D 2018
%P 307-322
%V 68
%N 2
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2018.0122-16/
%R 10.21136/CMJ.2018.0122-16
%G en
%F 10_21136_CMJ_2018_0122_16
Yue, Jun; Wei, Meiqin; Zhao, Yan. Proper connection number of bipartite graphs. Czechoslovak Mathematical Journal, Tome 68 (2018) no. 2, pp. 307-322. doi: 10.21136/CMJ.2018.0122-16

[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 | JFM

[2] Bondy, J. A., Murty, U. S. R.: Graph Theory. Graduate Texts in Mathematics 244, Springer, New York (2008). | DOI | MR | JFM

[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 | MR | JFM

[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 | MR

[5] Li, X., Shi, Y., Sun, Y.: Rainbow connections of graphs: a survey. Graphs Comb. 29 (2013), 1-38. | DOI | MR | JFM

[6] Li, X., Sun, Y.: Rainbow Connections of Graphs. Springer Briefs in Mathematics, Springer, New York (2012). | DOI | MR | JFM

[7] Li, X., Wei, M., Yue, J.: Proper connection number and connected dominating sets. Theor. Comput. Sci. 607 (2015), 480-487. | DOI | MR | JFM

Cité par Sources :