标题: | 排除混色圈的着色完全二分图 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 |
显示于类别: | Thesis |
文件中的档案:
If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.