Proper-walk connection number of graphs
From MaRDI portal
Abstract: 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 colours for every possible value of .
This page was built for publication: Proper-walk connection number of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6321296)
