仙人掌圖的強邊著色數

Abstract

一個圖G的強邊著色，是表示對圖G當中的邊的一個著色，使得距離不大於2的兩條邊都著不一樣的顏色。一個圖G的強邊著色數，以 χ_s'(G) 表示，則是在圖G的所有強邊著色中，所需要的最少顏色數。對於圖G，定義σ(G)是對於所有G當中的邊uv來說，(u的度數+v的度數－1)所可能達到的最大值。 一個仙人掌圖是表示一個圖當中的所有區塊都是一條邊或者一個圈的連通圖。在這篇論文中，我們研究仙人掌圖的強邊著色數。特別地，如果仙人掌圖G當中的每一個圈的長度都是6的倍數，則該圖的強邊著色數會等於σ(G)；如果仙人掌圖G當中的每一個圈的長度都是偶數，則該圖的強邊著色數會等於σ(G) 或者σ(G)+1。對於C5以外的一般仙人掌圖G，我們則有 χ_s'(G) ≤ ⌊(3σ(G)-1)/2⌋ 。 關鍵字：強邊著色數、仙人掌圖、圈、度數

A strong edge coloring of a graph G is an assignment of colors to the edges of G such that two distinct edges are colored differently if their distance is at most two. The strong chromatic index of a graph G, denoted by χ'_s(G) , is the minimum number of colors needed for a strong edge coloring of G. For a graph G, define σ(G)=〖max〗┬(uv∈E(G))⁡〖(d_G (u)+d_G (v)-1)〗, where d_G (x) is the degree of x. A cactus is a connected graph in which every block is an edge or a cycle. In this thesis, we study strong chromatic edge coloring for cacti. In particular, it is proved that for any cactus G, we have χ_s'(G) = σ(G) if the length of any cycle is a multiple of 6; χ_s'(G) ≤ σ(G)+1 if the length of any cycle is even; and χ_s'(G) ≤ ' ⌊(3σ(G)-1)/2⌋ in general except the case G = C5. Keywords: strong chromatic index, cactus, cycle, degree