Grossman and Ha ggkvist gave a sufficient condition under which a two-edgecoloured graph must have an alternating cycle (i.e., a cycle in which no two consecutive edges have the same colour). We extend their result to edge-coloured graphs with any number of colours. That is, we show that if there is no alternating cycle in an edge-coloured graph G, then G contains a vertex z such that no connected component of G&z is joined to z with edges of more than one colour. Our result implies that there is a polynomial-time algorithm for deciding whether an edge-coloured graph contains an alternating cycle.
1997 Academic Press
1. Introduction
In [3] Grossman and Ha ggkvist proved that if G is a graph whose edges are coloured either red or blue and there is no cycle in G whose edges are alternately red and blue, then the following holds. Either there is a vertex which is incident only with edges of the same colour or there is a separating vertex z such that no connected component of G&z is joined to z with both red and blue edges.
J. Bang-Jensen and G. Gutin (personal communication) asked whether Grossman and Ha ggkvist's result could be extended to edge-coloured graphs in general, where there is no constraint on the number of colours. In this note we give an affirmative answer to this question. That is, we show that if there is no alternating cycle in an edge-coloured graph G, then G contains a vertex z such that no connected component of G&z is joined to z with edges of more than one colour. It appears that Grossman and Ha ggkvist's proof cannot be used to obtain the desired extension. Our proof is therefore quite different from theirs, even though the proofs are comparable in length.
Using our extension, Bang-Jensen and Gutin [1] describe a polynomialtime algorithm for deciding whether an edge-coloured graph contains an article no. TB971728 222 0095-8956Γ97 25.00