完全图的强边着色

摘要

如果图G有一个合理边着色,且图G中所有顶点上的关联边着色集合都互不相同,则这种合理边着色又称为图G的强边着色.具有强边着色的图称为图G的强边着色图.使图G有强边着色的最小色数称为图G的强边色数.本文利用强边着色矩阵,讨论了完全图的强边着色及其分类,证明了:当n是奇数时,图Kn是一个第二类强边着色图,且x',(Kn)=△(Kn)+1;当n是偶数时,图Kn是一个第三类强边着色图,且x',(Kn)=△(Kn)+2.或者,x',(Kn)=3+2[n-2/2],这里[x]表示取小于、等于x的最大整数.