Edge-colored complete graphs with alternating cycles
type: Item
instance of: scholarly article
title: Edge-colored complete graphs with alternating cycles
zbMATH Open document ID: 0532.05030
DOI: 10.1016/0012-365X(83)90124-3
author: Sue Whitesides
published in: Discrete Mathematics
publication date: 1983-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 3843779
zbMATH Keywords: maximum color degree
zbMATH Keywords: alternating cycles
reviewed by: Bjarne Toft
MaRDI profile type: Publication
cites work: Alternating Hamiltonian cycles
cites work: Graphs with Hamiltonian cycles having adjacent lines different colours
cites work: Q4111595
cites work: Graphs with cycles having adjacent lines different colors
cites work: A property of the colored complete graph
full work available at URL: 0012-365x(83)90124-3
OpenAlex ID: W2039742259
Recommended article: Alternating cycles in edge-colored graphs
Recommended article: Q4320687
Recommended article: A note on alternating cycles in edge-coloured graphs
Recommended article: Color degree and alternating cycles in edge-colored graphs
Recommended article: Long Alternating Cycles in Edge-Colored Complete Graphs
Recommended article: Alternating paths in edge-colored complete graphs
Recommended article: Edge-colored complete graphs containing no properly colored odd cycles
Recommended article: Edge‐colored complete graphs without properly colored even cycles: A full characterization
Recommended article: The heterochromatic cycles in edge-colored graphs
Recommended article: Properly colored cycles of different lengths in edge-colored complete graphs
description: scientific article; zbMATH DE number 3843779