請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/65614
標題: | 圖的四類分解問題之研究 Four Partition Problems of Graphs |
作者: | Hsiang-Chun Hsu 徐祥峻 |
指導教授: | 張鎮華 |
關鍵字: | 最先適配著色數,最大著色問題,平衡分解數,奇偶邊染色數, first-fit chromatic numbers,max-coloring problem,balanced decomposition numbers,parity edge-chromatic numbers, |
出版年 : | 2012 |
學位: | 博士 |
摘要: | Partition problems of graphs are optimization problems about partitions of the vertex set V(G) or the edge set E(G) of a graph G under some additional restrictions. We begin this thesis by introducing some partition problems, basic definitions and notation in graph theory.
We study first-fit partitions and the first-fit chromatic numbers of graphs in Chapter 2. Given a family F of graphs satisfying that F is closed under taking induced subgraphs and e(G) ≤ dn(G) for any graph G ∈ F, where d is an arbitrary positive real number, we give an upper bound for the first-fit chromatic number of any graph in F. This result applies to d-degenerate graphs, planar graphs, and outerplanar graphs. A vertex-weighted graph (G,c) is a graph G with a positive weight c(v) on each vertex v in G. In Chapter 3, we study the max-coloring problem of a vertex-weighted graph (G,c), which attempts to partition V(G) into independent sets such that the sum of the maximum weight in each independent set is minimum. This is a weighted version of the usual vertex coloring problem of a graph. We give an upper bound for the number of sets needed in an optimal vertex partition of a vertex-weighted r-partite graph. We then derive the Nordhaus-Gaddum inequality for vertex-weighted graphs. We also consider the properties of the perfection on vertex-weighted graphs. A balanced coloring of a graph G is a partition {R,B,U} of V (G) with |R| = |B|, where R,B and U stand for the sets of red, blue and uncolored vertices in G, respectively. For a graph G with a balanced coloring {R,B,U}, an (R,B)-balanced decomposition is a partition P of V(G) such that the induced subgraph G[S] is connected and |S ∩ R| = |S ∩ B| for any S in P. The balanced decomposition number f(G) of a graph G is the minimum integer l such that for any balanced coloring (R,B) of G there is an (R,B)-balanced decomposition P with |S| ≤ l for S ∈ P. In Chapter 4, we give a shorter proof of a known result that a graph G has balanced decomposition number 3 if and only if G is [n(G)/2]-connected and G is not a complete graph. We then extend the definition of a balanced coloring using two colors to k colors, and call the corresponding parameter the balanced k-decomposition number. We compute the balanced k-decomposition numbers of trees and complete multipartite graphs. A parity edge-coloring of a graph G is an edge-coloring of G such that any path of positive length uses some color an odd number of times. A strong parity edge-coloring of a graph G is an edge-coloring of G such that any open walk uses some color an odd number of times. The parity (strong parity) edge-chromatic number of a graph G is the minimum number of colors used in a parity (strong parity) edge-coloring of G. In Chapter 5, we prove that, for 3 ≤ m ≤ n and n ≡ 0,−1,−2 (mod 2^{lceil lg m rceil}), the (strong) parity edge-chromatic number of the complete bipartite graph K_{m,n} is m◦n, the Hopf-Stiefel function, which is the least integer l such that C(l,k) is even for each k with l − n < k < m. We also consider the parity and the strong parity edge-chromatic numbers of the products of graphs. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/65614 |
全文授權: | 有償授權 |
顯示於系所單位: | 數學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-101-1.pdf 目前未授權公開取用 | 780.91 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。