Proper‐walk connection number of graphs

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 consecutiv...

Full description

Saved in:
Bibliographic Details
Published in:Journal of graph theory 2021-01, Vol.96 (1), p.137-159
Main Authors: Bang‐Jensen, Jørgen, Bellitto, Thomas, Yeo, Anders
Format: Article
Language:English
Subjects:
Apexes
Color
connected graph
connecting edge‐colouring
Graph theory
Graphs
Polynomials
proper connection by walks
strongly connected digraph
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0364-9024
1097-0118
DOI:10.1002/jgt.22609