This talks presents the result of joint work with Jørgen Bang-Jensen and Anders Yeo on the problem of connecting edge-colourings. A walk in an edge-coloured graph is said to be properly-coloured if and only if it does not use consecutively two edges of the same colour. Given a connected undirected 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. Determining whether this can be done with only two colours turns out to be the most challenging case.
We establish that the problem can be solved in polynomial time in the size of the graph and we provide a characterization of the graphs that can be connected with $k$ colours for every possible value of $k$.