Coloring graphs to produce properly colored walks (Q1684944)

Let \(G\) be a connected graph and \(\ell\) an edge labeling. A walk \(W\) or a path \(P\) between two vertices is properly colored with \(\ell\) if any two consecutive edges of \(W\) or \(P\), respectively, have different labels. The proper-walk connection number \(\operatorname{pW}(G)\) of \(G\) is the minimum number of labels needed, such that there exists a properly colored walk between each pair of vertices of \(G\). Similar the proper-path connection number \(\operatorname{pP}(G)\) is defined (by replacing walks with pats). A collection of results on \(\operatorname{pW}(G)\) and \(\operatorname{pP}(G)\) is presented on bipartite graphs, on graphs that contain two edge disjoint odd cycles, on 2-connected graphs, on bridgeless graphs and on unicyclic graphs. The most insight to the topic is provided by the first general result that \(\operatorname{pW}(G)\leq 3\) if \(G\) is a connected graph that different from a tree.