# 臺灣博碩士論文加值系統

(98.80.101.112) 您好！臺灣時間：2024/08/14 17:33

:::

### 詳目顯示

:

• 被引用:0
• 點閱:238
• 評分:
• 下載:0
• 書目收藏:0
 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)-balanceddecomposition 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.
 Acknowledgements . . . . . . . . . . iAbstract (in Chinese) . . . . . . . . . . iiAbstract (in English) . . . . . . . . . . iiiContents . . . . . . . . . . vList of Figures . . . . . . . . . . vii1 Introduction . . . . . . . . . . 11.1 Partition problems of graphs . . . . . . . . . . 11.2 Terminologies and notation in graph theory . . . . . . . . . . 72 First-fit chromatic numbers . . . . . . . . . . 132.1 Introduction . . . . . . . . . . 132.2 Graphs with bounded maximum average degree . . . . . . . . . . 172.3 Open problems and further works . . . . . . . . . . 233 Max-coloring of vertex-weighted graphs . . . . . . . . . . 243.1 Introduction . . . . . . . . . . 243.2 An upper bound on #χ(G,c) for r-partite graphs . . . . . . . . . . 263.3 Nordhaus-Gaddum inequality for χ(G,c) . . . . . . . . . . 293.4 Perfection of vertex-weighted graphs . . . . . . . . . . 313.5 Open problems and further works . . . . . . . . . . 354 Balanced decompositions . . . . . . . . . . 364.1 Introduction . . . . . . . . . . 364.2 Graphs with small balanced decomposition numbers . . . . . . . . . . 374.3 Balanced k-decomposition numbers . . . . . . . . . . 434.4 Graphs with high connectivity . . . . . . . . . . 444.5 Trees . . . . . . . . . . 464.6 Complete multipartite graphs . . . . . . . . . . 494.7 Open problems and further works . . . . . . . . . . 525 Parity edge-colorings . . . . . . . . . . 545.1 Introduction . . . . . . . . . . 545.2 Complete bipartite graphs . . . . . . . . . . 575.3 Products of graphs . . . . . . . . . . 635.4 Open problems and further works . . . . . . . . . . 67Bibliography . . . . . . . . . . 68
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 無相關期刊

 1 有限正交群的不變多項式 2 均曲率流的拉格拉奇自同構解 3 圖的均勻邊切割問題 4 整合生理回饋及呼吸偵測技術於呼吸行為改善之研究 5 氧化鐵奈米粒子對脂多醣活化小鼠微膠細胞功能之作用 6 臺灣一人一故事劇場操作內涵研究─以知了劇團為例 7 間隙流體對滾筒中鋼球顆粒流穩態行為之影響及相關影像處理之改進 8 高速氣動鑽具整合套杯式動靜壓混合氣壓軸承之設計開發與性能探究 9 潤濕性對微流道冷凝器熱傳熱傳增強之研究 10 使用於IEEE 802.11n規範中之低密度同位檢查碼解碼器硬體架構設計 11 社團活動對高中/職學生學習成就的影響 12 基於合成經驗模態解構法建立之類神經網路的匯率預測表現 13 企業取得或處分固定資產對公司股價及未來績效之影響 14 Gas6/Axl途徑在肝細胞癌中經由Slug調控腫瘤侵犯 15 LEF1在乳癌中藉由調控ERα促進其腫瘤生長

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室