Alternating Hamiltonian cycles. (English) Zbl 0325.05114

Bollobás, Béla; Erdős, Paul

Isr. J. Math. 23, 126-131 (1976).

For natural numbers \(n\) and \(d\), let \(K_n(\Delta_c \leq d)\) denote a complete graph of order \(n\) whose edges are colored so that no vertex belongs to more than \(d\) edges of the same color, and where \(\Delta_c\) is the maximal degree in the subgraph formed by the edges of color \(c\). D. E. Daykin proved that if \(d=2\) and \(n \geq 6\), then every such graph contains an alternating hamiltonian cycle (i.e. a spanning cycle whose adjacent edges have different colors). The authors have extended this as follows. Theorem: If \(69d <n\), then every \(G=K_n(\Delta_c \leq d)\) contains an alternating hamiltonian cycle. In fact, it is stated that if \(69d<n\), then every \(G=K_n(\Delta_c \leq d)\) contains alternating cycles of length \(\ell\) for every \(\ell\), \(3 \leq \ell \leq n\). An analogous result is obtained as follows. Let \(\chi_v\) denote the number of colors appearing among the edges containing the vertex \(v\), and let \(K_n(\chi_v \geq \lambda)\) denote a complete graph of order \(n\) whose edges are colored so that each vertex is on at least \(\lambda\) edges of different color. Theorem: Every \(K_n(\chi_v \geq (7/8)n)\) contains an alternating hamiltonian cycle. Several related results and conjectures are also presented.

Reviewer: S.F.Kapoor

MSC:

05C35	Extremal problems in graph theory
05C15	Coloring of graphs and hypergraphs

References:

[1]	D. E. Daykin,Graphs with cycles having adjacent lines different colours, to appear. · Zbl 0287.05105
[2]	Erdös, P.; Gallai, T., On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar., 10, 337-356 (1959) · Zbl 0090.39401 · doi:10.1007/BF02024498