標題: 排除混色圈的著色完全二分圖
Forbidding Multicolored Cycles in an Edge-colored Km,n
作者: 裴若宇
Pei, Ryo-Yu
傅恆霖
Fu, Hung-Lin
應用數學系所
關鍵字: 混色;完全二分;圈;排除;multicolored;complete bipartite;cycle;forbid
公開日期: 2008
摘要: 在一個邊已著色的圖中,若有一個子圖它的每個邊的顏色皆不相同,我們稱這種子圖為混色子圖。在這篇論文中,我們先整理了一些以往有關混色子圖的定理與猜測,我們將依照子圖的種類分成四類來介紹;接下來我們討論在一個完全二部圖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.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT009422524
http://hdl.handle.net/11536/81304
Appears in Collections:Thesis


Files in This Item:

  1. 252401.pdf