Proper-walk connection number of graphs

Jørgen Bang-Jensen*, Thomas Bellitto, Anders Yeo

*Kontaktforfatter for dette arbejde

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

2 Downloads (Pure)


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 (Formula presented.) colours for every possible value of (Formula presented.).

TidsskriftJournal of Graph Theory
Udgave nummer1 - Special Issue: Ron Graham
Sider (fra-til)137-159
StatusUdgivet - jan. 2021


Dyk ned i forskningsemnerne om 'Proper-walk connection number of graphs'. Sammen danner de et unikt fingeraftryk.