摘要
如果图G有一个合理边着色,且图G中所有顶点上的关联边着色集合都互不相同,则这种合理边着色又称为图G的强边着色。具有强边着色的图称为图G的强边着色图。使图G有强边着色的最小色数称为图G的强边色数。本文利用强边着色矩阵,讨论了完全图的强边着色及其分类,证明了:当n是奇数时,图Kn是一个第二类强边着色图,且χs′(Kn)=Δ(Kn)+1;当n是偶数时,图Kn是一个第三类强边着色图,且χs′(Kn)=Δ(Kn)+2。或者,χs′(Kn)=3+2[(n-2)/2],这里[x]表示取小于、等于x的最大整数。
If a graph G has a proper edge colourings such that the incident edge colourings sets between any two vertices in the graph G are different from each other, then such an edge colourings is said to be a strong edge colourings of graph G. The graph with a strong edge colourings is said to be the strong edge colourings graph. The minimum chromatic number to guarantee that the graph G has a strong edge colourings, is said to be the strong edge chromatic number of graph G. This paper uses the strong edge colourings matrix to discuss the strong edge colourings of complete graph and its classification, and proves that when n is odd, the graph K,, is the secondary class strong edge colourings graph and Х＇s（Kn） = A（Kn ） ＋ 1; and when n is even, the graph K, is the third class strong edge colourings graph and Х＇s（Kn）=△（Kn）＋2 .Or,Х＇s（Kn）=3＋2[n-2/2], here [x] expresses the maximum integer of ＂≤x ＂.
出处
《金陵科技学院学报》
2007年第3期1-4,共4页
Journal of Jinling Institute of Technology
关键词
完全图
强边着色矩阵
强边着色
强边色数
分类
complete graph
strong edge colourings
strong edge colourings matrix
strong edge chromatic number
classification
