排除混色圈的著色完全二分圖

Abstract

在一個邊已著色的圖中，若有一個子圖它的每個邊的顏色皆不相同，我們稱這種子圖為混色子圖。在這篇論文中，我們先整理了一些以往有關混色子圖的定理與猜測，我們將依照子圖的種類分成四類來介紹；接下來我們討論在一個完全二部圖Km,n中，是否存在一種恰用了n色的邊著色可以避免混色的圈出現，我們證明出來當2<=m<=n 及 n>=4時，在Km,n中一定會產生混色的C4。而在下列兩種情形：(1) m>=3 且 n>=9 或(2)m>=4 且n=7時，在Km,n中也會產生混色的C6。更進一步的，對於k<=m<=2k且k為奇數時，我們找到一種2k個顏色的著色法使得Km,2k 中能避免混色的C2k出現。

In an edge-colored graph, a subgraph whose edges are of distinct colors is known as a multicolored (or rainbow) subgraph. In this thesis, we shall first introduce several known results and conjectures related to multicolored subgraph in an edge-colored Kn,according to four categories of multicolored subgraphs. Then, we extend this study to consider whether there is a proper edge-coloring in a complete bipartite graph which forbids multicolored cycles. First, we claim that it is impossible to forbid multicolored 4-cycles in any proper n-edge-coloring of Km,n where 2 <= m<=n and n>=4. Second, we prove that any n-edge-colored Km,n (m<=n) contains a multicolored C6 if (i) m>=3 and n>=9; or (ii) m>=4 and n = 7. Finally, if k is odd, we obtain a proper 2k-edge-coloring of Km,2k which forbids multicolored (2k)-cycles where k<=m<=2k.