Polychromatic Hamilton cycles

DOI10.1016/0012-365X(93)90054-WMaRDI QIDQ685588zbMATH OpenWikidataFDO

Authors Bruce Reed, Alan Frieze

Publication date 17 October 1993

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(93)90054-W

zbMATH Keywords

coloredge-coloredHamiltonian cycle

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Review text

If the complete graph on \(n\) vertices is edge-colored such that the number of times that a color may occur is less than \(cn/\log(n)\), where \(c\) is a fixed constant, then there is a Hamiltonian cycle in which no two edges have the same color.

Recommendations

• Multicoloured Hamilton cycles
• Properly coloured Hamiltonian cycles in edge-coloured complete graphs
• Multicolored Hamilton cycles of the complete 3-uniform hypergraph
• scientific article; zbMATH DE number 1067836
• A remark on Hamilton cycles with few colors

Cites work

• Hamiltonian circuits in random graphs
• scientific article; zbMATH DE number 3825881 (Why is no real title available?)
• Path and cycle sub-Ramsey numbers and an edge-colouring conjecture
• Probability Inequalities for Sums of Bounded Random Variables

Cited in

(45)

• Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey
• The heterochromatic cycles in edge-colored graphs
• Multicolored parallelisms of Hamiltonian cycles
• Properly coloured Hamiltonian cycles in edge-coloured complete graphs
• Polychromatic cliques
• Multicoloured Hamilton cycles
• Labeled traveling salesman problems: complexity and approximation
• A note on equitable Hamiltonian cycles
• On Hamiltonian Berge cycles in [3]-uniform hypergraphs
• Disproof of a conjecture on the rainbow triangles in arc-colored digraphs
• Rainbow triangles in arc-colored digraphs
• Polychromatic colorings of 1-regular and 2-regular subgraphs of complete graphs
• Long directed rainbow cycles and rainbow spanning trees
• Extensions of results on rainbow Hamilton cycles in uniform hypergraphs
• Heterochromatic paths in edge colored graphs without small cycles and heterochromatic-triangle-free graphs
• Zeons, orthozeons, and graph colorings
• Rainbow Hamilton cycles and lopsidependency
• Long rainbow paths and rainbow cycles in edge colored graphs. A survey
• Rainbow \(C_4\)'s and directed \(C_4\)'s: the bipartite case study
• Sub-Ramsey numbers for matchings
• A remark on Hamilton cycles with few colors
• Totally multicoloured cycles
• Properly coloured copies and rainbow copies of large graphs with small maximum degree
• Multicolored Hamilton cycles of the complete 3-uniform hypergraph
• Elegantly colored paths and cycles in edge colored random graphs
• scientific article; zbMATH DE number 3855146 (Why is no real title available?)
• scientific article; zbMATH DE number 4073019 (Why is no real title available?)
• Rainbow \(C_3\)'s and \(C_4\)'s in edge-colored graphs
• Color the cycles
• scientific article; zbMATH DE number 54775 (Why is no real title available?)
• Color degree and heterochromatic cycles in edge-colored graphs
• scientific article; zbMATH DE number 845478 (Why is no real title available?)
• A note on color-bias Hamilton cycles in dense graphs
• Complexity of Computing the Anti-Ramsey Numbers for Paths.
• A rainbow blow-up lemma
• On rainbow cycles in edge colored complete graphs
• Colorful Hamilton Cycles in Random Graphs
• Color degree condition for long rainbow paths in edge-colored graphs
• Rainbow generalizations of Ramsey theory: A survey
• Approximating maximum edge 2-coloring by normalizing graphs
• Spectral properties of the zeon combinatorial Laplacian: cycles in finite graphs
• Complexity of computing the anti-Ramsey numbers for paths
• Approximating maximum edge 2-coloring by normalizing graphs
• On a problem of G. Hahn about coloured Hamiltonian paths in \(K_{2n}\)
• Anti-Ramsey properties of random graphs

This page was built for publication: Polychromatic Hamilton cycles

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