Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles
From MaRDI portal
Abstract: A subgraph of an edge-coloured complete graph is called rainbow if all its edges have different colours. In 1980 Hahn conjectured that every properly edge-coloured complete graph has a rainbow Hamiltonian path. Although this conjecture turned out to be false, it was widely believed that such a colouring always contains a rainbow cycle of length almost . In this paper, improving on several earlier results, we confirm this by proving that every properly edge-coloured has a rainbow cycle of length . One of the main ingredients of our proof, which is of independent interest, shows that a random subgraph of a properly edge-coloured formed by the edges of a random set of colours has a similar edge distribution as a truly random graph with the same edge density. In particular it has very good expansion properties.
Recommendations
- Long rainbow cycles and Hamiltonian cycles using many colors in properly edge-colored complete graphs
- Long directed rainbow cycles and rainbow spanning trees
- Rainbow Hamilton cycles in random regular graphs
- Long rainbow cycles in proper edge-colorings of complete graphs
- Almost all optimally coloured complete graphs contain a rainbow Hamilton path
Cites work
- A lower bound for the length of a partial transversal in a Latin square
- Counting sets with small sumset, and the clique number of random Cayley graphs
- Hamilton circuits with many colours in properly edge-coloured complete graphs.
- scientific article; zbMATH DE number 124525 (Why is no real title available?)
- scientific article; zbMATH DE number 1246230 (Why is no real title available?)
- Long rainbow cycles in proper edge-colorings of complete graphs
- On a problem of G. Hahn about coloured Hamiltonian paths in \(K_{2n}\)
- On rainbow cycles in edge colored complete graphs
- One-factorizations of the complete graph—A survey
- Path and cycle sub-Ramsey numbers and an edge-colouring conjecture
- Rainbow and orthogonal paths in factorizations of K_n
- Repeated communication and Ramsey graphs
- Testing triangle-freeness in general graphs
- The probabilistic method
Cited in
(34)- Edge-disjoint rainbow trees in properly coloured complete graphs
- Rainbow Hamiltonian cycles in strongly edge-colored graphs
- The \(n\)-queens completion problem
- Long directed rainbow cycles and rainbow spanning trees
- Embedding rainbow trees with applications to graph labelling and decomposition
- Rainbow vertex-pancyclicity of strongly edge-colored graphs
- A proof of Ringel's conjecture
- Some rainbow cycles in \(r\)-good edge-colorings
- Hypergraph cuts above the average
- Long rainbow cycles and Hamiltonian cycles using many colors in properly edge-colored complete graphs
- Long rainbow paths and rainbow cycles in edge colored graphs. A survey
- On odd rainbow cycles in edge-colored graphs
- Almost all optimally coloured complete graphs contain a rainbow Hamilton path
- Long rainbow cycles in proper edge-colorings of complete graphs
- Rainbow Turán problems for paths and forests of stars
- Rainbow cycles in flip graphs
- A rainbow blow-up lemma
- Rainbow structures in locally bounded colorings of graphs
- Lower bounds for rainbow Turan numbers of paths and other trees
- Repeated patterns in proper colorings
- Rainbow cycles in flip graphs
- On rainbow cycles in edge colored complete graphs
- Rainbow subgraphs in Hamiltonian cycle decompositions of complete graphs
- Hamilton transversals in random Latin squares
- Balanced edge-colorings avoiding rainbow cliques of size four
- Rainbow subgraphs in edge‐colored complete graphs: Answering two questions by Erdős and Tuza
- Rainbow subdivisions of cliques
- Transversal Hamilton cycle in hypergraph systems
- On the rainbow Turán number of paths
- Linearly many rainbow trees in properly edge-coloured complete graphs
- Towards Graham's rearrangement conjecture via rainbow paths
- Transversal Hamilton cycle in the hypergraph system
- Graph theory. Abstracts from the workshop held January 6--12, 2019
- Rainbow \(H\)-factors
This page was built for publication: Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1686315)
