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

Cité par Sources :