Proper-path colorings in graph operations

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. An edge coloring is a proper-path coloring of G if every pair u, v of distinct vertices of G are connected by a proper u - v path in G. The minimum number of colors required for a properpath coloring of G is the proper connection number pc(G) of G. We study proper-path colorings in those graphs obtained by some well-known graph operations, namely line graphs, powers of graphs, coronas of graphs and vertex or edge deletions. Proper connection numbers are determined for all iterated line graphs and powers of a given connected graph. For a connected graph G, sharp lower and upper bounds are established for the proper connection number of (i) the k-iterated corona of G in terms of pc(G) and k and (ii) the vertex or edge deletion graphs G - v and G - e where visa non-cut-vertex of G and e is a non-bridge of G in terms of pc(G) and the degree of v. Other results and open questions are also presented. © 2016 Charles Babbage Research Centre. All rights reserved.