邊著色圖中的混色子圖

Abstract

在一個邊著色的圖中（以下的邊著色須滿足相接的兩條邊必為不同顏色），如果有一個子圖它每個邊的顏色皆不相同，則稱這種子圖為一個混色圖。在這篇論文中，首先我們證明點數為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.