标题: 排除混色圈的着色完全二分图
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


文件中的档案:

  1. 252401.pdf

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.