theta圖的權重選擇性

Abstract

1, 2, 3猜想是由 M. Karoński等人於2004年所提出的邊權重點著色問題， 該問題由 T. Bartnicki等人於2009年推演成邊權重選擇性的問題。 儘管已經解決一些特殊的例子，這兩個問題現今仍尚未解決，也發展一些方法值得討論。 本文運用組合零點定理與積和式， 從環、theta圖與廣義theta圖著手發現一些結果。 其中最主要證明了這些圖皆為3-邊權重可選擇的。

The 1,2,3-conjecture is a problem of edge weight colorability of graphs which was posed by M. Karoński et al in 2004. Further problem of edge weight choosability of graphs was posed by T. Bartnicki et al in 2009. While being solved for some special cases, the two problems are still open nowadays. In this thesis, we use the combinatorial nullstellensatz and the permanent to find some results. We go through the cycles, then discuss the θ-graphs and generalized θ-graphs. The main result of this thesis is to show these graphs are all 3-edge weight choosable.