This paper studies the problem of proper-walk connection number: given an undirected connected graph, our aim is to colour its edges with as few colours as possible so that there exists a properly coloured walk between every pair of vertices of the graph i.e. a walk that does not use consecutively two edges of the same colour. The problem was already solved on several classes of graphs but still open in the general case. We establish that the problem can always be solved in polynomial time in the size of the graph and we provide a characterization of the graphs that can be properly connected with $k$ colours for every possible value of $k$.
翻译:本文研究了正确行走连接号的问题: 给一个未定向连接的图形, 我们的目标是用尽可能少的颜色来颜色它的边缘, 这样在图形的每对顶端之间就存在一种适当的彩色行走, 也就是说, 行走不使用同一颜色的连续两边。 问题已经在几类图表中解决, 但一般情况下还是开放的。 我们确认, 问题总是可以在图形大小的多元时间里解决, 我们提供图表的定性, 每一个可能的值都与$k$的颜色适当连接 。