Proper-walk connection number of graphs

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

*Kontaktforfatter

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

134 Downloads (Pure)

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

OriginalsprogEngelsk
TidsskriftJournal of Graph Theory
Vol/bind96
Udgave nummer1 - Special Issue: Ron Graham
Sider (fra-til)137-159
ISSN0364-9024
DOI
StatusUdgivet - jan. 2021

Fingeraftryk

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

Citationsformater