圖的權重選擇性

Abstract

1,2,3-猜想，是一個在距今約10年前被提出來的圖的權重選擇性的猜想。雖 然現在還是未被證明出來，但在近年來也已經有了很大的進展。於是就有人提出 了更高難度的猜想：3-重量可選猜想，並希望能藉由3-重量可選猜想的證明來順 便解決1,2,3-猜想這個問題。本篇論文主要是證明出來所有的完全多分圖、仙人 掌圖、餘圖以及距離繼承圖全部也都是3-重量可選的。

1,2,3 – conjecture, for the problem of weight choosability and which was posed by Karo’nski in 2004. Even though it is a unsolved problem in graph theory, someone proved it in some special cases of graphs. Bartnicki, Grytczuk and Niwczyk posed a more difficult conjecture: 3-weight choosable conjecture, and make a different approach for the problem. The main results of this thesis is to prove that complete r-partite graphs, cactus, cographs, and distance-hereditary graphs are 3-weight choosable.