混色同構圖的平行族

Abstract

在一個邊已著色的圖中，如果有一個子圖它每個邊的顏色皆不相同，則稱這種子圖為一個混色圖。在這篇論文中，首先我們先證明一個點數為2m的完全圖，其中m不等於2：在給一個2m-1個顏色的塗法後，可以將它分解成m個互相同構的混色懸掛樹。而對點數為2m+1的完全圖，我們也證明可以在著2m+1個顏色後將它分解成m個互相同構的混色哈米爾頓圈。第二部分，我們證明對於2m個點的完全圖，如果有一種2m-1個顏色的著色使得任兩種顏色均會形成一組C_4的分割，則這種著色的完全圖也可以分解成m個互相同構的混色懸掛樹。由這個結果，我們可以證明出在K_{2m}中，任意一種2m-1的邊著色，一定會存在兩個同構的混色懸掛樹。同樣地，對於點數為2m+1的完全圖，在任意的(2m+1)-邊著色下，也一定存在兩個同構的混色子圖，其中這個子圖是懸掛單圈圖。

A subgraph in an edge-colored graph is multicolored if all its edges receive distinct colors. In this thesis, we first prove that a complete graph on 2m (m not eaual to 2) vertices K_{2m} can be properly edge-colored with 2m-1 colors in such a way that the edges of K_{2m} can be partitioned into m multicolored isomorphic 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 (2m-1)-edge-coloring such that any two colors induce a 2-factor with each component a 4-cycle, then K_{2m} can be decomposed into m isomorphic multicolored spanning trees. As a consequence, we prove the existence of two isomorphic multicolored spanning trees in K_{2m} for each (2m-1)-edge-coloring of K_{2m}. As to the complete graph of odd order, we find two multicolored unicyclic isomorphic subgraphs in K_{2m+1} for each (2m+1)-edge coloring of K_{2m+1}.