全國中小學科展

平面圖的四元列表著色

科展類別

臺灣國際科展作品

屆次

2017年

科別

數學

得獎情形

一等獎

學校名稱

臺北市立第一女子高級中學

指導老師

楊宗穎

作者

林芮吟

關鍵字

平面圖,列表著色,放電論證法

摘要或動機

給定一個簡單圖G(simple graph ),令V(G)、E(G)分別為G的頂點與邊所形成的集合。對於兩個不同的頂點u, v∈V(G),若存在一條邊連結頂點u, v,則將此邊記為uv,以uv∈E(G)表示。給定函數f: V(G)→ℕ,若對任意的邊uv∈E(G),函數f皆滿足f(u)≠f(v),則稱函數f為圖G的一個著色函數(proper coloring)。對於圖G,任意給定每個頂點v∈V(G)一個可用的顏色清單L(v)⊂ℕ,其中清單內各有四個可用顏色(|L(v)|=4 ,每個頂點的顏色清單可以不相同),若總是存在一個著色函數f,滿足∀v∈V(G),f(v)∈L(v),則稱圖G為『可四元列表著色(4-choosable )』。對於平面圖( plane graph),針對長度較小的圈(cycle)進行限制,我們設計充分條件,使得滿足條件的平面圖為可四元列表著色。

平面圖的四元列表著色

Adobe Reader(Pdf)檔案