臺灣博碩士論文加值系統

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

Abstract (in English) . . . . . . . . . . . . . . . . . . i
Abstract (in Chinese) . . . . . . . . . . . . . . . . . .ii
Acknowledgement . . . . . . . . . . . . . . . . . . . . .iv
Contents . . . . . . . . . . . . . . . . . . . . . . . . vi
List of Figures . . . . . . . . . . . . . . . . . . . viii
List of Tables . . . . . . . . . . . . . . . . . . . . . x

1 Introduction and Preliminaries 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . 1
1.2 Graph Terms . . . . . . . . . . . . . . . . . . . . . 2
1.3 Edge-coloring . . . . . . . . . . . . . . . . . . . . 5
1.4 Basic Algebra . . . . . . . . . . . . . . . . . . . . 8
1.5 Latin Square . . . . . . . . . . . . . . . . . . . . 9
1.6 Parallelism Concept . . . . . . . . . . . . . . . . 11
1.7 Known Results . . . . . . . . . . . . . . . . . . . 12

2 Multicolored Tree Parallelism 16
2.1 Known Results . . . . . . . . . . . . . . . . . . . 16
2.2 Main Results . . . . . . . . . . . . . . . . . . . . 17

3 Multicolored Hamiltonian Cycle Parallelism 20
3.1 Known Results . . . . . . . . . . . . . . . . . . . 20
3.2 Main Results . . . . . . . . . . . . . . . . . . . . 22

4 Multicolored Spanning Trees in Edge-Colored
Complete Graphs 30
4.1 IsomorphicMulticolored Spanning Trees . . . . . . . .30
4.1.1 MST for C4-factor edge-colored K2m . . . . . . . . 30
4.1.2 Main Results . . . . . . . . . . . . . . . . . . . 34
4.2 Multicolored Spanning Trees . . . . . . . . . . . . 36
4.2.1 Recursive Construction . . . . . . . . . . . . . . 36
4.2.2 Main Results . . . . . . . . . . . . . . . . . . . 45

5 Multicolored Unicyclic Spanning Subgraphs in
Edge-Colored Complete Graphs 48
5.1 Isomorphic Multicolored Unicyclic Spanning Subgraphs 48
5.2 Multicolored Unicyclic Spanning Subgraphs . . . . . .51

6 Forbidden Multicolored Cycles 53
6.1 Multicolored Subgraphs in Edge-colored Complete
Graphs . . . . . . . . . . . . . . . . . . . . . . . 53
6.1.1 Multicolored Spanning Tree . . . . . . . . . . . . 54
6.1.2 Multicolored Path . . . . . . . . . . . . . . . . 54
6.1.3 Multicolored Cycle . . . . . . . . . . . . . . . . 55
6.2 Forbidding Multicolored Cycles in Edge-colored
Complete Bipartite Graphs . . . . . . . . . . . . . 57
6.2.1 Forbidding Multicolored 2k-cycles . . . . . . . . 57
6.2.2 Determining FMC(6) . . . . . . . . . . . . . . . . 60

7 Conclusion and Remarks 65

Bibliography 67

[1] S. Akbari and A. Alipour, Multicolored trees in complete graphs, J. Graph Theory 54(2006), 221-232.
[2] S. Akbari, A. Alipour, H. L. Fu and Y. H. Lo, Multicolored parallelisms of isomorphic spanning trees, SIAM J. Discrete Math. 20(2006), No. 3, 564-567.
[3] N. Alon, R. A. Brualdi and B. L. Shader, Multicolored forests in bipartite decomposition of graphs, J. Combin. Theory Ser. B 53(1991) 143-148.
[4] M. Albert, A. Frieze nd B. Reed, Multicolored Hamilton cycles, Electronic J. Combin. 2(1995), R10.
[5] R. B. Bapat, Mixed discriminants and spanning trees, Sankhy¯a Ser. A, 54(1992), 49-55.
[6] R. B. Bapat and G. M. Constantine, An enumerating function for spanning forests with color restrictions, Linear Algebra and Its Applications, 173(1992), 231-237.
[7] D. Banks, G. M. Constantine, A. Merriwether and R. LaFrance, Nonparametric inference on mtDNA mismatches, J. Nonparametre. Statist., 11(1999), 215-232.
[8] H. J. Broersma, X. Li, G. Woeginger and S. Zhang, Paths and cycles in colored graphs, Australasian J. Combin. 31(2005), 297-309.
[9] R. L. Brooks, On colouring the nodes of a network, Proc. Cambridge Phil. Soc. 37(1941), 194-197.
[10] R. A. Brualdi and S. Hollingsworth, Multicolored trees in complete graphs, J. Combin. Theory Ser. B 68 (1996), No. 2, 310-313.
[11] P. J. Cameron, Parallelisms of complete designs, London Math. Soc. Lecture Notes Series 23, Cambridge University Press, Cambridge, UK, 1976.
[12] H. Chen and X. Li, Long heterochromatic paths in edge-colored graphs, Electron. J. Combin. 12(2005), #R33.
[13] H. Chen and X. Li, Color degree and color neighborhood union conditions for long heterochromatic paths in edge-colored graphs, arXiv:math.CO/0512144 v1 7 Dec (2005).
[14] G. M. Constantine, Multicolored parallelisms of isomorphic spanning trees, Discrete Math. Theor. Comput. Sci. 5(2002), No. 1, 121-125.
[15] G. M. Constantine, Edge-disjoint isomorphic multicolored trees and cycles in complete graphs, SIAM J. Discrete Math. 18(2005), No. 3, 577-580.
[16] J. Denes and A. D. Keedwell, Latin Squares and Their Applications, Academic Press, New York, 1974.
[17] P. Erd˝os and T. Gallai, On maximal paths and circuits of graphs, Acta. Math. Acad. Sc. Hungar. 10(1959), 337-356.
[18] P. Erd˝os, J. Nesetril and V. Rodl, Some problems related to partitions of edges of a graph, Graphs and Other Combinatorial Topics, Teubner, Leipzig, (1983), 54-63.
[19] J. B. Fraleigh, A first course in abstract algebra, Pearson Education, U. S., 2003.
[20] H. L. Fu and Y. H. Lo, Multicolored parallelisms of Hamiltonian cycles, Discrete Math. 309(2009), No. 14, 4871-4876.
[21] H. L. Fu, Y. H. Lo and R. Y. Pei, Edge-colorings of Km,n which forbid multicolored cycles, Utilitas Mathematica, to appear.
[22] H. L. Fu and Y. H. Lo, Multicolored isomorphic spanning trees in complete graphs, Ars Combinatoria, to appear.
[23] H. L. Fu and Y. H. Lo, Multicolored spanning trees in edge-colored complete graphs, SIAM J. Discrete Math., revised.
[24] A. Frieze and B. Reed, Polychromatic Hamilton cycles, Discrete Math. 118(1993), 69-74.
[25] A. Gouge, D. Hoffman, P. Johnson, L. Nunley and L. Paben, Edge-colorings of Kn which forbid rainbow cycles, Utilitas Mathematica, to appear.
[26] F. Harari, Parallel comcepts in Graph Theory, Math. Comput. 18(1993), No. 7, 101-105.
[27] I. N. Herstein, Abstract algebra, John Wiley & Sons, New York, 1999.
[28] P. Hatami and P. W. Shor, A lower bound for the length of a partial transversal in a Latin square, J. Combin. Theory, Series A, 115(2008), 1103-1113.
[29] G. Hahn and C. Thomassen, Path and cycle sub-Ramsey numbers and an edge coloring conjecture, Discrete Math. 62(1986), 29-33.
[30] M. Jacroux, On the construction of sets of integers with equal power sums, J. Number Theory, 52(1995), No. 1, 35-42.
[31] M. Kano and X. L. Li, Monochromatic and Heterochromatic Subgraphs in Edge- Colored Graphs - A survey, Graphs and Combinatorics 24(2008), No. 4, 237-263.
[32] J. Krussel, S. Marshal and H. Verral, Spanning Trees Orthogonal to One-Factorizations of K2n, Ars Combin. 57(2000), 77-82.
[33] J. J. Montellano-Ballesteros and V. Neumann-Lara, An anti-Ramsey theorem on cycles, Graphs and Combinatorics, 21(2005), 343-354.
[34] V. G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz. 3(1964), 25-30.
[35] D. B. West, Introduction to Graph Theory, Prentice Hall, Upper Saddle River, NJ 07458, 2001.
[36] D. E. Woolbright and H. L. Fu, On the exists of rainbows in 1-factorizations of K2n, J. Combin. Des. 6(1998), 1-20.
[37] H. P. Yap, Total colourings of graphs, Lecture Notes in Mathematics, 1623. Springer-Verlag, Berlin, 1996.