平面圖的平方著色數
No Thumbnail Available
Date
2014
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
放電法(Discharging Method)最早在1977年，Appel使用來證明對於任何平面圖G，χ(G)≤4 (即四色定理)。而Heuvel等人在1999年，使用放電法證明了χ(G^2 )≤2"Δ"+25。在我們這篇論文中，將此上界降低至2"Δ"+10，加上涵蓋了前人的一些結果，我們並將這個結果推廣到λ(G;p,q)≤(4q-2)"Δ"+10p+8q-9。
Discharging method was proposed in 1977 by Appel and Haken, he used it to prove that for any planar graph G, χ(G)≤4, that is well-known 4-Color Theorem. Heuvel et al. used discharging method to prove χ(G^2 )≤2"Δ"+25 in1999. In this paper, we reduce this upper bound to 2"Δ"+10 and also generalize the result to λ(G;p,q)≤(4q-2)"Δ"+10p+8q-9.
Discharging method was proposed in 1977 by Appel and Haken, he used it to prove that for any planar graph G, χ(G)≤4, that is well-known 4-Color Theorem. Heuvel et al. used discharging method to prove χ(G^2 )≤2"Δ"+25 in1999. In this paper, we reduce this upper bound to 2"Δ"+10 and also generalize the result to λ(G;p,q)≤(4q-2)"Δ"+10p+8q-9.
Description
Keywords
平面圖, 著色數, 圖的標號, 放電法, planar graph, chromatic number, labeling of a graph, discharging