کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903839 | 1632961 | 2018 | 23 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Linearly many rainbow trees in properly edge-coloured complete graphs
ترجمه فارسی عنوان
به طور مداوم بسیاری از درختان رنگین کمان در نمودارهای کامل به لبه رنگی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
درختان رنگین کمان، لبه رنگ مناسب، تجزیه گراف،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
A subgraph of an edge-coloured complete graph is called rainbow if all its edges have different colours. The study of rainbow decompositions has a long history, going back to the work of Euler on Latin squares. In this paper we discuss three problems about decomposing complete graphs into rainbow trees: the Brualdi-Hollingsworth Conjecture, Constantine's Conjecture, and the Kaneko-Kano-Suzuki Conjecture. We show that in every proper edge-colouring of Kn there are 10â6n edge-disjoint spanning isomorphic rainbow trees. This simultaneously improves the best known bounds on all these conjectures. Using our method we also show that every properly (nâ1)-edge-coloured Kn has n/9â6 edge-disjoint rainbow trees, giving further improvement on the Brualdi-Hollingsworth Conjecture.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 132, September 2018, Pages 134-156
Journal: Journal of Combinatorial Theory, Series B - Volume 132, September 2018, Pages 134-156
نویسندگان
Alexey Pokrovskiy, Benny Sudakov,