We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Proper‐walk connection number of graphs.
- Authors
Bang‐Jensen, Jørgen; Bellitto, Thomas; Yeo, Anders
- 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, that is, 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.
- Subjects
GRAPH connectivity; POLYNOMIAL time algorithms; UNDIRECTED graphs; GRAPH coloring
- Publication
Journal of Graph Theory, 2021, Vol 96, Issue 1, p137
- ISSN
0364-9024
- Publication type
Article
- DOI
10.1002/jgt.22609