Journal of Combinatorics
Volume 3 (2012)
Proper connection with many colors
Pages: 683 – 693
We say an edge-colored graph is properly connected if, between every pair of vertices, there exists a properly colored path. For a graph $G$, define the proper connection number $pc(G)$ to be the minimum number of colors $k$ such that there exists a $k$-coloring of $E(G)$ which is properly connected. In this work, we study conditions on $G$ which force upper bounds on $pc(G)$.
proper edge-coloring, connectivity, proper connection, alternating paths