Embedding rainbow trees with applications to graph labelling and decomposition

DOI10.4171/JEMS/982MaRDI QIDQ2216732

Richard Montgomery, Benjamin Sudakov, Alexey Pokrovskiy

Publication date: 17 December 2020

Published in: Journal of the European Mathematical Society (JEMS) (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1803.03316

zbMATH Keywords

treesgraph labelinggraph decompositionrainbow subgraphs

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items (18)

The \(n\)-queens completion problem ⋮ Spanning trees in dense directed graphs ⋮ Graph Tilings in Incompatibility Systems ⋮ The novel generally described graphs for cyclic orthogonal double covers of some circulants ⋮ A Short proof of the blow-up lemma for approximate decompositions ⋮ Finding large rainbow trees in colourings of \(K_{n, n}\) ⋮ Perfectly packing graphs with bounded degeneracy and many leaves ⋮ Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022 ⋮ Graph and hypergraph packing ⋮ Tree decompositions of graphs without large bipartite holes ⋮ A rainbow blow‐up lemma ⋮ A rainbow blow-up lemma for almost optimally bounded edge-colourings ⋮ A proof of Ringel's conjecture ⋮ Repeated Patterns in Proper Colorings ⋮ Packing Paths in Steiner Triple Systems ⋮ Rainbow factors in hypergraphs ⋮ Pseudorandom hypergraph matchings ⋮ Unnamed Item

Cites Work

• An approximate version of the tree packing conjecture
• Packing minor-closed families of graphs into complete graphs
• On a problem of G. Hahn about coloured Hamiltonian paths in \(K_{2n}\)
• Transversals of latin squares and their generalizations
• An \(n\times n\) Latin square has a transversal with at least \(n-\sqrt n\) distinct symbols
• Orthogonal double covers of complete graphs by trees
• A dynamic survey of graph labeling
• Packing of graphs and permutations -- a survey
• Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles
• Packing of graphs - a survey
• Long directed rainbow cycles and rainbow spanning trees
• Optimal packings of bounded degree trees
• Packing degenerate graphs
• Packing spanning graphs from separable families
• Rainbow and orthogonal paths in factorizations ofKn
• Hamilton circuits with many colours in properly edge-coloured complete graphs.
• On Additive Bases and Harmonious Graphs
• On orthogonal double covers by trees
• A blow-up lemma for approximate decompositions
• Packing trees of unbounded degrees in random graphs
• Almost all trees are almost graceful
• A Combinatorial Theorem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Embedding rainbow trees with applications to graph labelling and decomposition