Rainbow spanning trees in randomly coloured G_k-out

2022/10/04 by Deepak Bal, Alan Frieze, Bal, Deepak +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2210.01327

openalex publication_date 2022/10/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given a graph G=(V,E) on n vertices and an assignment of colours to its edges, a set of edges S ⊆ E is said to be rainbow if edges from S have pairwise different colours assigned to them. In this paper, we investigate rainbow spanning trees in randomly coloured random G_k-out graphs.

Related

• Rainbow trees in uniformly edge-coloured graphs
• Rainbow spanning trees in random subgraphs of dense regular graphs
• Rainbow copies of spanning subgraphs
• Rainbow spanning trees in properly coloured complete graphs
• Rainbow subgraphs of uniformly coloured randomly perturbed graphs