Publication: On proper-path colorings in graphs
0
0
Issued Date
2016
Resource Type
File Type
application/pdf
ISSN
8353026
Other identifier(s)
2-s2.0-84976345191
Rights Holder(s)
Scopus
Bibliographic Citation
Journal of Combinatorial Mathematics and Combinatorial Computing. Vol 97, (2016), p.189-207
Suggested Citation
Andrews E., Lumduanhom C., Laforge E., Zhang P. On proper-path colorings in graphs. Journal of Combinatorial Mathematics and Combinatorial Computing. Vol 97, (2016), p.189-207. Retrieved from: https://hdl.handle.net/20.500.14740/5424
Author(s)
Abstract
Let G be an edge-colored connected graph. A path P is a proper path in G if no two adjacent edges of P are colored the same. If P is a proper u - v path of length d(u, v), then P is a proper u - v geodesic. An edge coloring c is a proper-path coloring of a connected graph G if every pair u, v of distinct vertices of G are connected by a proper u - v path in G and c is a strong proper coloring if every two vertices u and v are connected by a proper u - v geodesic in G. The minimum number of colors used a proper-path coloring and strong proper coloring of G are called the proper connection number pc(G) and strong proper connection number spc(G) of G, respectively. These concepts are inspired by the concepts of rainbow coloring, rainbow connection number rc(G), strong rainbow coloring and strong connection number src(G) of a connected graph G. The numbers pc(G) and spc(G) are determined for several well-known classes of graphs G. We investigate the relationship among these four edge colorings as well as the well-studied proper edge colorings in graphs. Furthermore, several realization theorems are established for the five edge coloring parameters, namely pc(G), spc(G), rc(G), src(G) and the chromatic index of a connected graph G. © 2016, Charles Babbage Research Centre. All rights reserved.