Proper-walk connection number of graphs

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

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

8 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.).

Original languageEnglish
JournalJournal of Graph Theory
Volume96
Issue number1 - Special Issue: Ron Graham
Pages (from-to)137-159
ISSN0364-9024
DOIs
Publication statusPublished - Jan 2021

Keywords

  • connected graph
  • connecting edge-colouring
  • proper connection by walks
  • strongly connected digraph

Fingerprint

Dive into the research topics of 'Proper-walk connection number of graphs'. Together they form a unique fingerprint.

Cite this