完全三分圖K(1,m,n)的IC-著色研究

A Study of IC-coloring of K(1,m,n)

張敏南(Min-nan Chang)

指導教授 ： 劉立民

中原大學/理學院/應用數學研究所/碩士(2009年)

https://doi.org/10.6840/cycu200900751

摘要

令G為一個連通圖,且f是從圖G頂點集V(G)映至正整數集合N的函數;對於每個圖G中的子圖H,定義fs(H)=,另外我們將fs(G)記為S(f).如果對每一個正整數k在[1,S(f)],都存在一個圖G的連通子圖H,使得fs(H)=k,那麼f就稱為圖G的一個IC-著色.如果M(G)=max{fs(G):f為為圖 的一個IC-著色},則稱M(G)為圖G的IC-指數.若f為圖G的IC-著色且S(f)=M(G),則稱f為圖G的一個極大IC-著色.
在這篇論文中,我們先找到了一個完全三分圖K(1,2,n)的IC-指數下界,並證明K(1,2,n)的IC-指數為 .以此K(1,2,n)的著色為基礎,可以建構一個K(1,m,n)的著色關係,本文也證明其為一個IC-著色,故K(1,m,n)的IC-指數

關鍵字

IC-著色 ； IC-指數

並列摘要

Let G be a connected graph. Giving a coloring f:V(G)->N of G, and any subgraph H of G, we define fs(H)= and denote fs(G)=S(f). The function is called an IC-coloring of G if for any k in the set [1,S(f)], there exist an induced connected subgraph H of G, such that fs(H)=k. The IC-index of a graph G, denoted byM(G), is defined to be M(G)=max{fs(G):f is an IC-coloring of G } We say f is a maximal IC-colorng of G if f is an IC-coloring of G with fs(G)=M(G).
In this thesis, we find the lower bound of the IC-index of K(1,2,n) and then prove that the IC-index of K(1,2,n) is . We also find an IC-coloring of K(1,m,n) and obtain that .

並列關鍵字

IC-index ； IC-coloring

參考文獻

Technical Reports, 95-26(1995), pp. 1-9.

NJ07458: Prentice Hall.

[4] E. Salehi, S. Lee and M. Khatirinejad, IC-Colorings and IC-Indices of graphs,

Discrete Mathematics, 299(2005), pp. 297-310.

[6] C. L. Shiue and H. L. Fu, The IC-Indices of complete bipartite graphs, Electronic J.