Extremal stretch of proper-walk coloring of graphs

摘要

Let G be an edge-colored connected graph, a path (trail, walk) of G is said to be a proper-path (trail, walk) if any two adjacent edges of it are colored distinctly. If there is a proper-path (trail, walk) between each pair of different vertices of G, then G is called proper-path (trail, walk) connected. The edge-coloring which makes G proper-path (trail, walk) connected is called a proper-path (trail, walk) coloring. The minimum number of colors required in a proper-path (trail, walk) coloring is referred to as the proper-path (trail, walk) connection number of G. In J. Bang-Jensen, T. Bellitto and A. Yeo, Proper-walk connection number of graphs, J. Graph Theory 96(2020) 137–159, the authors investigated the graphs with proper-walk connection number k and suggested to study the stretch of proper-walk coloring. In this note, we consider the stretch of proper-walk (path, trail) coloring and present some tight upper bounds.