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$ is connected by a proper $u-v$ path in $G$. The minimum number of colors required for a proper-path coloring of $G$ is the proper connection number $\text{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 $\text{pc}(G)$ and $k$, and (ii) the vertex or edge deletion graphs $G-v$ and $G-e$, where $v$ is a non-cut-vertex of $G$ and $e$ is a non-bridge of $G$, in terms of $\text{pc}(G)$ and the degree of $v$. Other results and open questions are also presented.