完全k-部圖 -- 來自

完全k-部圖

一個完全 -部圖是一個 k-部圖（即，圖頂點的集合被分解為個不相交的集合，使得同一集合內的任意兩個圖頂點都不相鄰），並且來自不同集合的每對圖頂點都相鄰。如果這個集合中分別有 , , ..., 圖頂點，則完全 -部圖記為 -部圖記為。上圖顯示了完全三部圖。

符號有時用來表示 (Brouwer et al. 1989, p. 478)。

對於某個而言，如果是完全k-部圖的圖被稱為完全多部圖 (Chartrand and Zhang 2008, p. 41)。完全多部圖可以在多項式時間內透過有限禁忌子圖特徵來識別，因為完全多部圖是 -free 的（其中是路徑圖路徑圖的圖補圖）。

形狀為 , , ... 的完全多部圖在 Wolfram 語言中實現為CompleteGraph[p, q, ...].

圖蘭圖是一個完全多部圖，其部集的大小盡可能接近相等 (Gross and Yellen 2006, p. 476)。

特殊情況總結在下表中。

當 >=2 時，完全部圖具有哈密頓 [準哈密頓] 分解當且僅當且是偶數 [奇數] (Bosák 1990, p. 124)。

參考文獻

Bosák, J. 圖的分解。 New York: Springer, 1990.

Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. 距離正則圖。 New York: Springer-Verlag, 1989.

Chartrand, G. and Zhang, P. 圖著色理論。 Boca Raton, FL: Chapman and Hall/CRC, 2008.

Gross, J. T. and Yellen, J. 圖論及其應用，第二版。 Boca Raton, FL: CRC Press, pp. 476-477, 2006.

Harary, F. 圖論。 Reading, MA: Addison-Wesley, p. 23, 1994.

Saaty, T. L. and Kainen, P. C. 四色問題：進攻與征服。 New York: Dover, p. 12, 1986.

Skiena, S. "完全

-部圖。" §4.2.2 in 離散數學實現：組合數學和圖論與 Mathematica。 Reading, MA: Addison-Wesley, pp. 142-144, 1990.

完全k-部圖