Brualdi and Hollingsworth conjectured in Brualdi and Hollingsworth (1996) that in any complete graph K2n, n≥3, which is properly colored with 2n−1 colors, the edge set can be partitioned into n edge disjoint rainbow spanning trees (where a graph is said to be rainbow if its edges have distinct colors). Constantine (2002) strengthened this conjecture asking the rainbow spanning trees to be pairwise isomorphic. He also showed an example satisfying his conjecture for every 2n∈{2s:s≥3}∪{5⋅2s,s≥1}. Caughmann, Krussel and Mahoney (2017) recently showed a first infinite family of edge colorings for which the conjecture of Brualdi and Hollingsworth can be verified. In the present paper, we extend this result to all edge-colorings arising from cyclic 1-factorizations of K2n constructed by Hartman and Rosa (1985). Finally, we remark that our constructions permit to extend Constatine's result also to all 2n∈{2sd:s≥1,d>3odd}.

Rainbow spanning tree decompositions in complete graphs colored by cyclic 1-factorizations / Rinaldi, G.; Mazzuoccolo, G.. - In: DISCRETE MATHEMATICS. - ISSN 0012-365X. - 342:4(2019), pp. 1006-1016.

Rainbow spanning tree decompositions in complete graphs colored by cyclic 1-factorizations

Rinaldi G.
;
2019

Abstract

Brualdi and Hollingsworth conjectured in Brualdi and Hollingsworth (1996) that in any complete graph K2n, n≥3, which is properly colored with 2n−1 colors, the edge set can be partitioned into n edge disjoint rainbow spanning trees (where a graph is said to be rainbow if its edges have distinct colors). Constantine (2002) strengthened this conjecture asking the rainbow spanning trees to be pairwise isomorphic. He also showed an example satisfying his conjecture for every 2n∈{2s:s≥3}∪{5⋅2s,s≥1}. Caughmann, Krussel and Mahoney (2017) recently showed a first infinite family of edge colorings for which the conjecture of Brualdi and Hollingsworth can be verified. In the present paper, we extend this result to all edge-colorings arising from cyclic 1-factorizations of K2n constructed by Hartman and Rosa (1985). Finally, we remark that our constructions permit to extend Constatine's result also to all 2n∈{2sd:s≥1,d>3odd}.
apr-2019
342
4
1006
1016
Rainbow spanning tree decompositions in complete graphs colored by cyclic 1-factorizations / Rinaldi, G.; Mazzuoccolo, G.. - In: DISCRETE MATHEMATICS. - ISSN 0012-365X. - 342:4(2019), pp. 1006-1016.
Rinaldi, G.; Mazzuoccolo, G.
File in questo prodotto:
File Dimensione Formato  
Rainbow_trees_FINAL_VERSION_24092018.pdf

non disponibili

Descrizione: articolo principale
Tipologia: Post-print dell'autore (bozza post referaggio)
Dimensione 321.05 kB
Formato Adobe PDF
321.05 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
1-s2.0-S0012365X18304217-main.pdf

non disponibili

Tipologia: Versione dell'editore (versione pubblicata)
Dimensione 393.88 kB
Formato Adobe PDF
393.88 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11380/1169956
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact