Berge路徑分割猜測的研究

Abstract

令Ｐ是一個由路徑(path)所形成的集合。若Ｐ裡的路徑兩兩交集為空集合，而且Ｐ中所有路徑的點聯集為圖Ｇ所有的點，則Ｐ是圖Ｇ的一組路徑分割(path partition)。令ｋ是一個正整數，則我們對任一組路徑分割Ｐ可以定義它的k範數(k-norm)。若一組路徑分割擁有最小的k範數，則此路徑分割被稱為是最優化的k範數分割。 令C^k是圖Ｇ的一組k著色，即圖Ｇ中k個由點形成的獨立集所成之集合，而且兩兩獨立集交集為空集合。若路徑分割Ｐ裡任一條路徑中有min{|P_i|,k}個點分別落在C^k裡不同的獨立集，則稱此k著色C^k正交於路徑分割Ｐ。Berge猜測對於任一組最優化的k範數分割，都可找到一組k著色正交於此最優化的k範數分割。 這個猜測至今尚未被解決，只有一些特別的情形被證明；而在這篇論文裡，我們藉由一些特殊的圖來驗證Berge的猜測是對的。