On proper-path colorings in graphs

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.