Edge-colored complete graphs with alternating cycles

Let \(\Delta\) denote the maximum number of edges of the same colour meeting at a common vertex in an edge colouring of the complete n-graph \(k_ n\). \textit{D. E. Daykin} [J. Comb. Theory, Ser. B 20, 149-152 (1976; Zbl 0287.05105)] proved that for \(\Delta =2\) and \(n\geq 6\) there are cycles with adjacent edges of different colours (called alternating cycles) of all possible lengths 3 through n. It seems to be an unsolved problem for how big \(\Delta\) the conclusion still holds. \textit{B. Bollobás} and \textit{P. Erdős} [Isr. J. Math. 23, 126-131 (1976; Zbl 0325.05114)] proved that \(\Delta<n/69\) is sufficient, and further improvements were obtained by \textit{C. C. Chen} and \textit{D. E. Daykin} [J. Comb. Theory, Ser. B21, 135-139 (1976; Zbl 0287.05106)] and \textit{J. Shearer} [Discrete Math. 25, 175-178 (1979; Zbl 0397.05024)]. In the present paper it is proved that for \(1<\Delta<n-2\) and \(n>6\) there are cycles of all possible lengths 3 through n with no \(\Delta\) consecutive edges of the same colour.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Edge-colored complete graphs with alternating cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q788736)