Proper connection of graphs

AbstractAn edge-colored graph G is k-proper connected if every pair of vertices is connected by k internally pairwise vertex-disjoint proper colored paths. The k-proper connection number of a connected graph G, denoted by pck(G), is the smallest number of colors that are needed to color the edges of G in order to make it k-proper connected. In this paper we prove several upper bounds for pck(G). We state some conjectures for general and bipartite graphs, and we prove them for the case when k=1. In particular, we prove a variety of conditions on G which imply pc1(G)=2