Almost all optimally coloured complete graphs contain a rainbow Hamilton path

Stephen Gould; Tom Kelly; Daniela Kuhn; Deryk Osthus

doi:10.1016/j.jctb.2022.04.003

Almost all optimally coloured complete graphs contain a rainbow Hamilton path

Stephen Gould, Tom Kelly, Daniela Kuhn, Deryk Osthus

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

A subgraph H of an edge-coloured graph is called rainbow if all of the edges of H have different colours. In 1989, Andersen conjectured that every proper edge-colouring of K_n admits a rainbow path of length n-2. We show that almost all optimal edge-colourings of K_nadmit both (i) a rainbow Hamilton path and (ii) a rainbow cycle using all of the colours. This result demonstrates that Andersen's Conjecture holds for almost all optimal edge-colourings of K_nand answers a recent question of Ferber, Jain, and Sudakov. Our result also has applications to the existence of transversals in random symmetric Latin squares.

Original language	English
Pages (from-to)	57-100
Number of pages	44
Journal	Journal of Combinatorial Theory. Series B
Volume	156
Early online date	3 May 2022
DOIs	https://doi.org/10.1016/j.jctb.2022.04.003
Publication status	E-pub ahead of print - 3 May 2022

Keywords

Andersen's conjecture
Edge-colouring
Rainbow path
Rainbow cycle
Hypergraph matchings
Distributive absorption
Latin squares

Access to Document

10.1016/j.jctb.2022.04.003Licence: Creative Commons: Attribution (CC BY)

GouldS2022AlmostFinal published version, 824 KBLicence: Creative Commons: Attribution (CC BY)

Cite this

@article{ad20c07913624d0fa4a7d1ac8150a08e,

title = "Almost all optimally coloured complete graphs contain a rainbow Hamilton path",

abstract = "A subgraph H of an edge-coloured graph is called rainbow if all of the edges of H have different colours. In 1989, Andersen conjectured that every proper edge-colouring of Kn admits a rainbow path of length n-2. We show that almost all optimal edge-colourings of Kn admit both (i) a rainbow Hamilton path and (ii) a rainbow cycle using all of the colours. This result demonstrates that Andersen's Conjecture holds for almost all optimal edge-colourings of Kn and answers a recent question of Ferber, Jain, and Sudakov. Our result also has applications to the existence of transversals in random symmetric Latin squares.",

keywords = "Andersen's conjecture, Edge-colouring, Rainbow path, Rainbow cycle, Hypergraph matchings, Distributive absorption, Latin squares",

author = "Stephen Gould and Tom Kelly and Daniela Kuhn and Deryk Osthus",

year = "2022",

month = may,

day = "3",

doi = "10.1016/j.jctb.2022.04.003",

language = "English",

volume = "156",

pages = "57--100",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Elsevier",

}

TY - JOUR

T1 - Almost all optimally coloured complete graphs contain a rainbow Hamilton path

AU - Gould, Stephen

AU - Kelly, Tom

AU - Kuhn, Daniela

AU - Osthus, Deryk

PY - 2022/5/3

Y1 - 2022/5/3

N2 - A subgraph H of an edge-coloured graph is called rainbow if all of the edges of H have different colours. In 1989, Andersen conjectured that every proper edge-colouring of Kn admits a rainbow path of length n-2. We show that almost all optimal edge-colourings of Kn admit both (i) a rainbow Hamilton path and (ii) a rainbow cycle using all of the colours. This result demonstrates that Andersen's Conjecture holds for almost all optimal edge-colourings of Kn and answers a recent question of Ferber, Jain, and Sudakov. Our result also has applications to the existence of transversals in random symmetric Latin squares.

AB - A subgraph H of an edge-coloured graph is called rainbow if all of the edges of H have different colours. In 1989, Andersen conjectured that every proper edge-colouring of Kn admits a rainbow path of length n-2. We show that almost all optimal edge-colourings of Kn admit both (i) a rainbow Hamilton path and (ii) a rainbow cycle using all of the colours. This result demonstrates that Andersen's Conjecture holds for almost all optimal edge-colourings of Kn and answers a recent question of Ferber, Jain, and Sudakov. Our result also has applications to the existence of transversals in random symmetric Latin squares.

KW - Andersen's conjecture

KW - Edge-colouring

KW - Rainbow path

KW - Rainbow cycle

KW - Hypergraph matchings

KW - Distributive absorption

KW - Latin squares

U2 - 10.1016/j.jctb.2022.04.003

DO - 10.1016/j.jctb.2022.04.003

M3 - Article

VL - 156

SP - 57

EP - 100

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

SN - 0095-8956

ER -

Almost all optimally coloured complete graphs contain a rainbow Hamilton path

Abstract

Keywords

Access to Document

Fingerprint

Cite this