Please use this identifier to cite or link to this item:
標題: 圖的T-調著色數研究
The study on the t-tone chromatic number of some graphs
作者: 楊俊彥
Jyun-Yan Yang
關鍵字: T-調著色數;緊緻t-調著色;t-tone chromatic number;tight t-tone coloring
引用: [1] D. Bal, P. Bennett, A. Dudek, A. Frieze, The t-Tone Chromatic Number of Random Graphs, Graphs and Combinatorics, 30 (2014), Issue 5, 1073–1086. [2] A. Bickle, B. Phillips, t-Tone Colorings of Graphs, submitted (2011). [3] D. W. Cranston, J. Kim, W. B. Kinnersley, New results in t-tone coloring of graphs, Electron. J. Combin, 20 (2013), no. 2, #P17. [4] N. Fonger, J. Goss, B. Phillips, C. Segroves, Math 6450: Final Report. [5] J. Loe, D. Middelbrooks, A. Morris, K. Wash, 2-tone colorings in graph products, Discuss. Math. Graph Theory, 35 (2015), no. 1, 55–72. [6] J.-J. Pan, C.-H. Tsai, A lower bound for the t-tone chromatic number of a graph in terms of Wiener index, Graphs Combin, 34 (2018), no.1, 159-162. [7] D. West, Introduction to Graph Theory, (2nd ed.). Prentice Hall,(2001).
若圖G 上的著色函數將每個點都對應到從k 個顏色中取t 個相異顏色,且任意兩點的之間重複的顏色數量小於這兩點之間的距離,則稱這個函數為圖G 的t-調k-著色。圖G 的t-調著色數是滿足圖G 的t-調k-著色存在的最小整數k,記作 t(G)。
潘教授與他的研究生蔡同學證明了當 τt(G) = |V|t− W (G)+ (|V| choose 2) 若且為若 t ≥ max_{v∈V} ∑_{V (G)−{v}}(d(u,v) − 1),W(G) 是圖G 的維納數。
我們利用輔助圖來重新解釋這個結果。並用我們的方法來得到特殊圖的緊緻t-調著色以及當t小於max_{v∈V} ∑_{V (G)−{v}}(d(u,v) − 1)時,圖的t-調著色數的上界。

A t-tone k-coloring of a graph G = (V,E) is a function f : V → ([k] choose t) such that |f (u) ∩ f (v)| < d(u,v) for all distinct vertices u and v. The t-tone chromatic number of G, denoted τt(G) is the smallest integer k such that G has a t-tone k-coloring.
Pan and Tsai [6] showed that if and only if τt(G) = t|V |− W (G)+ (|V| choose 2) if and only if t ≥ max_{v∈V} ∑_{V (G)−{v}}(d(u,v) − 1), where W (G) is the Wiener index of G. We give a reinterpretation of this result by using an auxiliary graph G∗.
Using our method, we get the tight t-tone coloring of some special graphs and the upper bound for general graphs when t is less than max_{v∈V} ∑_{V (G)−{v}}(d(u,v) − 1).
Rights: 同意授權瀏覽/列印電子全文服務,2018-08-16起公開。
Appears in Collections:應用數學系所

Files in This Item:
File SizeFormat Existing users please Login
nchu-107-7104053004-1.pdf1.11 MBAdobe PDFThis file is only available in the university internal network    Request a copy
Show full item record

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.