臺灣博碩士論文加值系統

所謂的時間圖 (Time graph) 指的是每一個點可以一一對應至一個在實數線上的單位區間，當兩個點所對應的區間交集非空，則這兩個點有邊連。在這一篇文章中，我們主要證明了最大度為奇數的時間圖均為第一類圖，且提出了一個時間圖為第二類圖的充分必要條件猜測，並得到了一些相關的結果。

A graph G is called a time graph if its vertices can be put into one-to-one correspondence with a set of unit intervals of a linearly ordered set (like a real line) such that two vertices are connected by an edge of G if and only if their corresponding intervals have nonempty intersection. In this thesis, we mainly get that the graph G is of class 1 if maximum degree is odd. We also offer a conjecture in the third chapter to classify a time graph and get some results.

中文摘要……………………………………………i.
英文摘要……………………………………………ii.
誌 謝……………………………………………iii.
目 錄……………………………………………iv.
第一章：定義與介紹………………………………1.
第二章：主要結果…………………………………10.
參考文獻……………………………………………27.

[1] L. W. Beineke and R. J. Wilson, On the edge-chromatic number of a graph, Discrete Math. 5(1973)15-20. MR 47-4836.
[2] J. A. Bondy and U. S. R. Murty, Graph theory with applications. Elsevier North Holland, Inc., (1976).
[3] B. L. Chen and H. L. Fu, Total chromatic number and chromatic index of split graphs. JCMCC 17(1995), 137-146.
[4] A. G. Chetwynd and A. J. W. Hilton, Star multigraphs with three vertices of maximum degree, Math. Proc. Phil. Soc., 100(1986), 303-317.
[5] S. Fiorini and R. J. Wilson, Edge-colorings of graphs, Pitman, London(1977).
[6] J. C. Fournier, Colorations des aretes d'un graphe. Cahiers du CERO, 15(1973), 311-314.[7] M. C. Golumbic, Algorithmic graph theory and perfect graphs, Academic, New York(1980).
[8] A. J. W. Hilton, Definitions of criticality with respect to edge-coloring, J. Graph Theory 1(1977), 61-68.
[9] M. J. Plantholt, The chromatic index of graphs with a spanning star, J. Graph Theory 5(1981), 5-13.
[10] M. J. Plantholt, The chromatic index of graphs with large maximum degree, Discrete Math. 47(1983), 91-96.
[11] V. G. Vizing, On an estimate of the chromatic class of a p-graph (Russian). Diskret. Analiz.,3(1964), 25-30.