圖的權重選擇性

Weight Choosability of Graphs

郭俊彥(Chun-Yen Kuo)

指導教授 ： 張鎮華

國立臺灣大學/理學院/數學研究所/碩士(2013年)

https://doi.org/10.6342/NTU.2013.00802

摘要

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

並列關鍵字

weight choosability ； 3-weight choosable ； complete r-partite graphs ； cactus ； cograph ； distance-hereditary graph

參考文獻

[1] L. Addario-Berry, R. E. L. Aldred, K. Dalal and B. A. Reed, Vertex colouring edge partitions, J. Combin. Theory Ser. B 94 (2005), 237-244.

[3] S. Akbari, E. Ehsani and P. Jalaly Khalilabadi. Submitted to European Journal of Combinatorics (2011).

[4] N. Alon, Combinatorial Nullstellensatz, Combin. Prob. Comput. 8 (1999), 7-29.

[5] N. Alon and M.Tarsi, Anowhere-zero point in linear mappings, Combinatorica 9 (1989), 393-395.

[6] H.J. Bandelt and H.M. Mulder Distance{hereditary graphs J. Combin. Theory Ser. B 41 (1986), 182-208.