Proper connection number of bipartite graphs

Jun Yue; Meiqin Wei; Yan Zhao

Czechoslovak Mathematical Journal (2018)

  • Volume: 68, Issue: 2, page 307-322
  • ISSN: 0011-4642

Abstract

top
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 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 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 δ ( G ) ≥ 2 and a dominating cycle or a dominating complete bipartite subgraph, which implies pc ( G ) = 2 . Furthermore, we get that the proper connection number of connected bipartite graphs with δ ≥ 2 and diam ( G ) ≤ 4 is two.

How to cite

top

Yue, Jun, Wei, Meiqin, and Zhao, Yan. "Proper connection number of bipartite graphs." Czechoslovak Mathematical Journal 68.2 (2018): 307-322. <http://eudml.org/doc/294416>.

@article{Yue2018,
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)\ge 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 \ge 2$ and $\{\rm diam\}(G)\le 4$ is two.},
author = {Yue, Jun, Wei, Meiqin, Zhao, Yan},
journal = {Czechoslovak Mathematical Journal},
keywords = {proper coloring; proper connection number; bipartite graph; dominating set},
language = {eng},
number = {2},
pages = {307-322},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Proper connection number of bipartite graphs},
url = {http://eudml.org/doc/294416},
volume = {68},
year = {2018},
}

TY - JOUR
AU - Yue, Jun
AU - Wei, Meiqin
AU - Zhao, Yan
TI - Proper connection number of bipartite graphs
JO - Czechoslovak Mathematical Journal
PY - 2018
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 68
IS - 2
SP - 307
EP - 322
AB - 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)\ge 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 \ge 2$ and ${\rm diam}(G)\le 4$ is two.
LA - eng
KW - proper coloring; proper connection number; bipartite graph; dominating set
UR - http://eudml.org/doc/294416
ER -

References

top
  1. Andrews, E., Lumduanhom, C., Laforge, E., Zhang, P., On proper-path colorings in graphs, J. Comb. Math. Comb. Comput. 97 (2016), 189-207. (2016) Zbl1347.05055MR3524734
  2. Bondy, J. A., Murty, U. S. R., 10.1007/978-1-84628-970-5, Graduate Texts in Mathematics 244, Springer, New York (2008). (2008) Zbl1134.05001MR2368647DOI10.1007/978-1-84628-970-5
  3. Borozan, V., Fujita, S., Gerek, A., Magnant, C., Manoussakis, Y., Montero, L., Tuza, Z., 10.1016/j.disc.2011.09.003, Discrete Math. 312 (2012), 2550-2560. (2012) Zbl1246.05090MR2935404DOI10.1016/j.disc.2011.09.003
  4. Li, X., Magnant, C., 10.20429/tag.2015.000102, Theory and Applications of Graphs 0 (2015), Article 2, 30 pages. (2015) MR2606615DOI10.20429/tag.2015.000102
  5. Li, X., Shi, Y., Sun, Y., 10.1007/s00373-012-1243-2, Graphs Comb. 29 (2013), 1-38. (2013) Zbl1258.05058MR3015944DOI10.1007/s00373-012-1243-2
  6. Li, X., Sun, Y., 10.1007/978-1-4614-3119-0, Springer Briefs in Mathematics, Springer, New York (2012). (2012) Zbl1250.05066MR3183989DOI10.1007/978-1-4614-3119-0
  7. Li, X., Wei, M., Yue, J., 10.1016/j.tcs.2015.06.006, Theor. Comput. Sci. 607 (2015), 480-487. (2015) Zbl1333.05227MR3429068DOI10.1016/j.tcs.2015.06.006

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.