標題: 邊著色圖中的混色子圖
Multicolored Subgraphs in an Edge-colored Graphs
作者: 羅元勳
Lo, Yuan-Hsun
傅恆霖
Fu, Hung-Lin
應用數學系所
關鍵字: 邊著色;混色子圖;分割;完全圖;edge-coloring;multicolored subgraph;partition;complete graph
公開日期: 2009
摘要: 在一個邊著色的圖中(以下的邊著色須滿足相接的兩條邊必為不同顏色),如果有一個子圖它每個邊的顏色皆不相同,則稱這種子圖為一個混色圖。在這篇論文中,首先我們證明點數為2m的完全圖(m≠2),存在一個2m−1個顏色的邊著色,可以將K_{2m}分解成m個互相同構的混色懸掛樹。而對點數為2m+1的完全圖,我們也證明其邊適當地著2m+1個顏色後,K_{2m+1}將可分解成m個混色的哈米爾頓圈。 第二部分,我們證明對於2m個點的完全圖,如果有一種2m−1個顏色的邊著色使得任兩種顏色均會形成一組C_4的分割,則這種著色的完全圖也可以分解成m個互相同構的混色懸掛樹。由這個結果,我們可以證明在K_{2m}中(m≥14),任意給定一種2m−1個顏色的邊著色,一定會存在三個同構的混色懸掛樹。至於對於點數為2m+1的完全圖,在任意的2m+1個顏色邊著色下,也一定存在兩個同構的混色子圖,其中這兩個子圖是懸掛單圈圖。 若捨棄掉「同構」這個限制,我們利用一種遞迴的建構方法,可以證明出在K_{2m}中,任意給定一種2m−1個顏色的邊著色,存在約Ω(√m)個邊互斥的混色懸掛樹。利用相同的策略-遞迴建構法,在K_{2m−1}中,任意給定一種2m−1個顏色的邊著色,我們也可找出約Ω(√m)個邊互斥的混色懸掛單圈圖。 最後,我們討論如何在一個邊著色的完全二部圖中避免某些特定 的混色子圖的出現。我們的貢獻有下列兩部分:(1) 對任意的k≥2,如果n≥5k−6,則任意n著色的完全二部圖K_{k,n}中一定找得到混色的C_{2k};(2) 刻劃出所有可避免混色C_6的完全二部圖。
A subgraph in an edge-colored graph is multicolored if all its edges receive distinct colors. In this dissertation, we first prove that a complete graph of order 2m (m≠2) can be properly edge-colored with 2m−1 colors in such a way that the edges of K_{2m} can be partitioned into m isomorphic multicolored spanning trees. Then, for the complete graph on 2m+1 vertices, we give a proper edge-coloring with 2m+1 colors such that the edges of K{2m+1} can be partitioned into m multicolored Hamiltonian cycles. In the second part, we first prove that if K_{2m} admits a proper (2m−1)-edge-coloring such that any two colors induce a 2-factor with each component a 4-cycle, then K2m can be partitioned into m isomorphic multicolored spanning trees. As a consequence, we show the existence of three isomorphic multicolored spanning trees whenever m≥14. As to the complete graph of odd order, two multicolored isomorphic unicyclic spanning subgraphs can be found in an arbitrary proper (2m+1)-edge-coloring of K{2m+1}. If we drop the condition “isomorphic”, we prove that there exist Ω(√m) mutually edge-disjoint multicolored spanning trees in any proper (2m−1)-edge-colored K_{2m} by applying a recursive construction. Using an analogous strategy, we can also find Ω(√m) mutually edge-disjoint multicolored unicyclic spanning subgraphs in any proper (2m−1)-edge-colored K_{2m−1}. Finally, we consider the problem of how to forbid a specific multicolored subgraph in a properly edge-colored complete bipartite graph. We (1) prove that for any integer k≥2, if n≥5k−6, then any properly n-edge-colored K_{k,n} contains a multicolored C2k, and (2) determine the order of the properly edge-colored complete bipartite graphs which forbid multicolored 6-cycles.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT079522802
http://hdl.handle.net/11536/41210
Appears in Collections:Thesis


Files in This Item:

  1. 280201.pdf