Proper-walk connection number of graphs

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

*Kontaktforfatter for dette arbejde

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Abstrakt

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
ISSN0364-9024
DOI
StatusE-pub ahead of print - 30. jun. 2020

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

  • Citationsformater