圓盤維度為二的平面圖其著色性質之研究

Abstract

令$G$為一平面圖。我們稱$G$是圓盤維度為二的,如果$G$的所有的頂點可 嵌入在兩個稱為圓盤的互斥環路上,而且所有$G$的邊不是落在此二圓盤之 邊界上就是落在此二圓盤之外部且邊與邊之間沒有交叉。將$d$定義為三 角形間的最短距離,也就是說,連接不同三角形之頂點的所有最短路徑之長 度之最小值。在本篇論文之中我們首先在第二章中瀏覽一些以前與三色問 題有關的結果,然後在第三章中我們證明了所有圓盤維度為二且$d \geq 1$之平面圖皆是頂點三可著色的。 Let $G$ be a planar graph. $G$ is called "with $disk$ $dimension$ two" if all vertices of $G$ can be embedded on two disjoint cycles called $disks$, in which no edge lie in its interiors and make no crossing. Defined $d$ as the minimum distance of triangles, $i.e.$ the minimum length of shortest paths joining vertices of different triangles. In this thesis, we first study the 3-color problem in Chapter 2, and in Chapter 3 we show that if $G$ is a planar graph with disk dimension two and $d \geq 1$ then $G$ is 3-colorable.