Partitioning Complete Graphs by Heterochromatic Trees

(整期优先)网络出版时间:2012-04-14
/ 1
Aheterochromatictreeisanedge-coloredtreeinwhichanytwoedgeshavedifferentcolors.Theheterochromatictreepartitionnumberofanr-edge-coloredgraphG,denotedbytr(G),istheminimumpositiveintegerpsuchthatwhenevertheedgesofthegraphGarecoloredwithrcolors,theverticesofGcanbecoveredbyatmostpvertex-disjointheterochromatictrees.Inthispaperwedeterminetheheterochromatictreepartitionnumberofr-edge-coloredcompletegraphs.Wealsofindatmosttr(Kn)vertex-disjointheterochromatictreestocoveralltheverticesinpolynomialtimeforagivenr-edge-coloringofKn.