ในทฤษฎีกราฟซึ่งเป็นส่วนหนึ่งของคณิตศาสตร์ กราฟ k-ส่วนคือกราฟที่จุดยอดสามารถแบ่งออกเป็นk เซตอิสระที่แตกต่างกันได้ หรือ กล่าวอีกนัยหนึ่งคือ กราฟที่สามารถระบายสีด้วยkสี โดยที่ไม่มีจุดปลายสองจุดใดของเส้นขอบที่มีสีเดียวกัน เมื่อk = 2จะเรียกว่ากราฟสองส่วนและเมื่อk = 3จะเรียกว่ากราฟ สามส่วน

กราฟสองส่วนอาจได้รับการตรวจสอบในเวลาพหุนามแต่สำหรับk > 2 ใดๆ การทดสอบว่าเป็นกราฟkส่วน หรือไม่นั้น เป็น ปัญหา NP-complete เมื่อกำหนดกราฟที่ไม่มีการระบายสี ^{[ 1 ]} อย่างไรก็ตาม ในบางแอปพลิเคชันของทฤษฎีกราฟ กราฟ kส่วนอาจถูกป้อนเป็นอินพุตสำหรับการคำนวณโดยที่การระบายสีถูกกำหนดไว้แล้ว ซึ่งสามารถเกิดขึ้นได้เมื่อเซตของจุดยอดในกราฟแสดงถึงวัตถุประเภทต่างๆ ตัวอย่างเช่นโฟล์กโซโนมีได้รับการจำลองทางคณิตศาสตร์โดยกราฟสามส่วน ซึ่งเซตของจุดยอดสามเซตในกราฟแสดงถึงผู้ใช้ของระบบ ทรัพยากรที่ผู้ใช้กำลังติดแท็ก และแท็กที่ผู้ใช้ได้ใช้กับทรัพยากร^{[ 2 ]}

ตัวอย่างกราฟk -partite ที่สมบูรณ์

กราฟของทรงแปดเหลี่ยมK _2,2,2

กราฟ K _3,3,3 ของ ทรงแปดเหลี่ยมทั่วไปเชิงซ้อน

กราฟ K _2,2,2,2 ของ เซลล์ 16 เซลล์

กราฟk -partite สมบูรณ์คือ กราฟ k -partite ที่มีขอบเชื่อมระหว่างจุดยอดทุกคู่จากเซตอิสระที่แตกต่างกัน กราฟเหล่านี้อธิบายด้วยสัญลักษณ์ที่มีตัวอักษรK ตัวใหญ่ ตามด้วยลำดับของขนาดของแต่ละเซตในการแบ่งส่วน ตัวอย่างเช่นK _2,2,2คือ กราฟ tripartite สมบูรณ์ของทรงแปดเหลี่ยมปกติซึ่งสามารถแบ่งออกเป็นสามเซตอิสระ โดยแต่ละเซตประกอบด้วยจุดยอดตรงข้ามสองจุดกราฟ multipartite สมบูรณ์คือ กราฟที่เป็นk -partite สมบูรณ์สำหรับk บาง ค่า^{[ 3 ]} กราฟTuránเป็นกรณีพิเศษของกราฟ multipartite สมบูรณ์ ซึ่งเซตอิสระมีขนาดแตกต่างกันไม่เกินหนึ่งจุดยอด กราฟ k -partite สมบูรณ์ กราฟ multipartite สมบูรณ์ และกราฟส่วนเติมเต็ม ของกราฟเหล่านี้ คือ กราฟคลัสเตอร์เป็นกรณีพิเศษของcographและสามารถจดจำได้ในเวลาพหุนาม แม้ว่าการแบ่งส่วนจะไม่ได้ระบุไว้ในข้อมูลนำเข้าก็ตาม