摘要

首先，我們定義圖G之邊的著色數為使得圖G的相鄰兩邊不能塗相同顏色的最少顏色數。同時，我們定義了圖G 的點最大維度為△(G)，那很明顯的，△(G)≦χ1。另一方面，Vizing證明了χ1 (G) ≦△(G) + 1。

本篇論文主要的目的是在研究完全r 分圖及完全分裂圍之邊著色數。比較特別地，我們證明了當m1<m2≦m3 時χ1( Km l, m2, m3) = △(Km1, m2, m3)。但在完全3分圖的情況下，當m1, m2, m3均為奇數及m1= m2≦m3-2時仍未解出，那對於完全4分圖己全部作出，結果是這樣子的，當m1= m2 = m3 =m4 - 1時，χ1( Km1, m2,m3, m4) =△(Km l, m2, m3, m4) + 1，否則χ1 (Kml , m2 , m3 , m4) = △(Kml , m3 , m3 , m4)。

ABSTRACT

The chromatic index x1 (G) of a (simple) graph G is the smallest positive integer k such that there is a mapping from the edge set E(G) to (1, 2, ... , k} with the property that no two adjacent edges have the same image. Denoted by △(G) the maximum valency of a vertex in G. It is clear that △(G) ≦ x 1 (G). On theo ther hand, Vizing showed that x1 (G) ≦ △(G) + 1.

The main purpose of this thesis is to study the chromatic indices of complete r-partite graphs and complete split graphs. In particular, we prove that x t (Kml , m2 ,m3) = ~ (Km1, m2, m3) when m1 < m2 ≦ m3. The case when rn3 is odd and m1 = rn2 ≦ rn3 - 2 still unknown. The results for complete 4-partite graphs are also known. Xl (K.ml,m2,m3,m4)= △(Kml,rn2,m3,m4) + 1, when m1 = rn2 = m3 = m4 - 1; otherwise, x 1 (Km1, m2, m3, m4) = △(Kml, m2, m3, m4).

REFERENCES

[1] M. Behzad. G. Chartrand and J. K. Cooper. The color number of complete graphs, J. London Hath. Soc (1967) 226-228.
[2] L. W. Beineke and R. J. Wilson. On the edge-chromatic number of a graph, Discrete Math (1973) 15-20.
[3] C. Berge, Graphs and Hypergraphs, North-Holland, Amsterdam(1973)
[4] J. A. Bondy and U.S.R. Murty, Graph Theory with Applications,Elseuier, New york (1976)
[5] R. Laskar and W. Hare. Chromatic numbers for certain graphs,J. London Hath. Soc(2), 4 (1972), 489-492.
[6] V. G. Vizing, On an estimate of the chromatic class of a p-graph,Diskret. Analiz (1964) 25-30.
[7] V. G. Vizing, The chromatic class of a multigraph. Kibernetika V (Kiev) (1965) 29-39 / Cybernetics (1965) 32-41.
[8] M. Plantholt, The chromatic index of graphs with a spanning star, J. Graph Theory, Vol.5(1981) 45-53