Edge-colored complete graphs with alternating cycles (Q788736)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Edge-colored complete graphs with alternating cycles |
scientific article |
Statements
Edge-colored complete graphs with alternating cycles (English)
0 references
1983
0 references
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.
0 references
maximum color degree
0 references
alternating cycles
0 references