Brualdi and Hollingswort conjectured in Brualdi and Hollingsworth (1996) that in any completegraph K 2 n , n ≥ 3,whichisproperlycoloredwith2 n − 1colors,theedgesetcanbe partitionedinto n edgedisjointrainbowspanningtrees(whereagraphissaidtoberainbow ifitsedgeshavedistinctcolors).Constantine(2002)strengthenedthisconjectureaskingthe rainbowspanningtreestobepairwiseisomorphic.Healsoshowedanexamplesatisfying hisconjectureforevery2 n ∈{ 2 s : s ≥ 3 }∪{ 5 · 2 s , s ≥ 1 } .Caughmann,KrusselandMahoney (2017)recentlyshowedafirstinfinitefamilyofedgecoloringsforwhichtheconjectureof BrualdiandHollingsworthcanbeverified.Inthepresentpaper,weextendthisresulttoall edge-coloringsarisingfromcyclic1-factorizationsof K 2 n constructedbyHartmanandRosa (1985).Finally,weremarkthatourconstructionspermittoextendConstatine’sresultalso toall2 n ∈{ 2 s d : s ≥ 1 , d > 3odd } .
Rainbow spanning tree decompositions in complete graphs colored by cyclic 1-factorizations
G. Mazzuoccolo;
2019-01-01
Abstract
Brualdi and Hollingswort conjectured in Brualdi and Hollingsworth (1996) that in any completegraph K 2 n , n ≥ 3,whichisproperlycoloredwith2 n − 1colors,theedgesetcanbe partitionedinto n edgedisjointrainbowspanningtrees(whereagraphissaidtoberainbow ifitsedgeshavedistinctcolors).Constantine(2002)strengthenedthisconjectureaskingthe rainbowspanningtreestobepairwiseisomorphic.Healsoshowedanexamplesatisfying hisconjectureforevery2 n ∈{ 2 s : s ≥ 3 }∪{ 5 · 2 s , s ≥ 1 } .Caughmann,KrusselandMahoney (2017)recentlyshowedafirstinfinitefamilyofedgecoloringsforwhichtheconjectureof BrualdiandHollingsworthcanbeverified.Inthepresentpaper,weextendthisresulttoall edge-coloringsarisingfromcyclic1-factorizationsof K 2 n constructedbyHartmanandRosa (1985).Finally,weremarkthatourconstructionspermittoextendConstatine’sresultalso toall2 n ∈{ 2 s d : s ≥ 1 , d > 3odd } .
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
