ในทฤษฎีกราฟการระบายสีแบบแพ็คกิ้ง ( เรียกอีกอย่างว่าการระบายสีแบบกระจาย ) เป็นการ ระบายสีกราฟประเภทหนึ่งโดยที่จุดยอดจะได้รับสี (แทนด้วยจำนวนเต็มบวก) โดยที่ระยะห่างระหว่างจุดยอดสองจุดใดๆ ที่มีสีเดียวกันจะต้องมากกว่าจำนวนสีแบบแพ็คกิ้ง (หรือจำนวนสีแบบกระจาย ) (หรือ) ของกราฟคือจำนวนสีขั้นต่ำที่จำเป็นสำหรับการระบายสีแบบแพ็คกิ้ง^{[ 1 ]}${\displaystyle i}$${\displaystyle i}$${\displaystyle \chi _{\rho }(G)}$${\displaystyle \chi _{b}(G)}$${\displaystyle G}$

การระบายสีแบบบรรจุของกราฟคือฟังก์ชันที่ถ้าแล้วระยะทางค่าต่ำสุดสำหรับการระบายสีดังกล่าวคือ จำนวนโครมา ติกแบบบรรจุ^{[ 1 ]}${\displaystyle G=(V,E)}$${\displaystyle \pi :V\to \{1,2,\ldots ,k\}}$${\displaystyle \pi (u)=\pi (v)}$${\displaystyle d(u,v)>\pi (u)}$${\displaystyle k}$${\displaystyle \chi _{\rho }(G)}$

ในทำนองเดียวกัน การระบายสีการบรรจุคือการแบ่งเซตจุดยอด โดยแต่ละจุดยอดเป็นการบรรจุแบบ (จุดยอดที่มีระยะห่างระหว่างคู่มากกว่า) ^{[ 1 ]}${\displaystyle {\mathcal {P}__{\pi }=\{V_{1},V_{2},\ldots ,V_{k}\}}$${\displaystyle V_{i}}$${\displaystyle i}$${\displaystyle i}$

สำหรับกราฟใดๆที่มีจุดยอด: ${\displaystyle G}$${\displaystyle n}$

• ${\displaystyle \omega (G)\leq \chi (G)\leq \chi _{\rho }(G)}$โดยที่คือจำนวนคลิกและคือจำนวนสี^{[ 1 ]}${\displaystyle \omega (G)}$${\displaystyle \chi (G)}$
• ${\displaystyle \chi _{\rho }(G)\leq \alpha _{0}(G)+1}$โดยที่จำนวนการปกคลุมจุดยอดจะเท่ากันก็ต่อเมื่อมีเส้นผ่านศูนย์กลางสอง^{[ 1 ]}${\displaystyle \alpha _{0}(G)}$${\displaystyle G}$
• ${\displaystyle \chi _{\rho }(G)\leq n-\alpha (G)+1}$โดยที่หมายเลขความเป็นอิสระคือ^{[ 2 ]}${\displaystyle \alpha (G)}$
• ถ้าเช่นนั้น^{[ 2 ]}${\displaystyle \chi _{\rho }(G)=\chi (G)}$${\displaystyle \omega (G)=\chi (G)}$

การพิจารณาว่าสามารถแก้ไขได้ในเวลาพหุนามหรือไม่ ในขณะที่พิจารณาว่าเป็น ปัญหา NP-hardหรือไม่ แม้แต่สำหรับกราฟระนาบ^{[ 1 ]}${\displaystyle \chi _{\rho }(G)\leq 3}$${\displaystyle \chi _{\rho }(G)\leq 4}$

ปัญหายังคงเป็น NP-hard สำหรับ กราฟ เส้นผ่านศูนย์กลาง 2 เนื่องจากการคำนวณจำนวนการปกคลุมจุดยอดเป็น NP-hard สำหรับกราฟดังกล่าว^{[ 1 ]}

ปัญหาดังกล่าวเป็นปัญหา NP-complete สำหรับต้นไม้^{[ 2 ]}ซึ่งเป็นการแก้ปัญหาคำถามที่ค้างคามานาน อย่างไรก็ตาม สามารถแก้ไขได้ในเวลาพหุนามสำหรับกราฟที่มีtreewidthและ diameter ที่จำกัด^{[ 2 ]}

สำหรับกราฟเส้นทาง : ${\displaystyle P_{n}}$

• ${\displaystyle \chi _{\rho }(P_{n})=2}$สำหรับ${\displaystyle 2\leq n\leq 3}$
• ${\displaystyle \chi _{\rho }(P_{n})=3}$สำหรับ${\displaystyle n\geq 4}$

สำหรับกราฟวงจร ที่มี: ${\displaystyle C_{n}}$${\displaystyle n\geq 3}$

• ${\displaystyle \chi _{\rho }(C_{n})=3}$ถ้าเป็นหรือเป็นพหุคูณของ${\displaystyle n}$${\displaystyle 3}$${\displaystyle 4}$
• ${\displaystyle \chi _{\rho }(C_{n})=4}$มิฉะนั้น

สำหรับต้นไม้ ลำดับ: ^{[ 1 ]}${\displaystyle T}$${\displaystyle n}$

• ${\displaystyle \chi _{\rho }(T)\leq (n+7)/4}$สำหรับต้นไม้ทั้งหมด ยกเว้นต้นไม้ที่มีจุดยอดเฉพาะสองต้น${\displaystyle P_{4}}$${\displaystyle 8}$
• กราฟรูปดาว มี${\displaystyle K_{1,n-1}}$${\displaystyle \chi _{\rho }(K_{1,n-1})=2}$
• ต้นไม้ที่มีเส้นผ่านศูนย์กลาง${\displaystyle 3}$${\displaystyle \chi _{\rho }(T)=3}$
• ขอบเขตนั้นคมชัดและเกิดขึ้นจากการสร้างโครงสร้างต้นไม้แบบเฉพาะเจาะจง${\displaystyle (n+7)/4}$

สำหรับกราฟไฮเปอร์คิวบ์^{[ 1 ] [ 3 ]}${\displaystyle Q_{k}}$

• ${\displaystyle \chi _{\rho }(Q_{k})\sim {\frac {1}{2}}\cdot O(1/k)\cdot 2^{k}}$เชิงอะซิมโทติก
• กับ...:${\displaystyle k=1,2,3,4}$

${\displaystyle \chi _{\rho }(Q_{k})=2,3,5,7,15,25,49,95}$... (ลำดับA335203ในOEIS )

สำหรับกราฟฉบับสมบูรณ์ : ${\displaystyle K_{n}}$

• ${\displaystyle \chi _{\rho }(K_{n})=n}$
• ${\displaystyle \chi _{\rho }(S(K_{n}))=n+1}$สำหรับ${\displaystyle n\geq 3}$

สำหรับกราฟสองส่วนที่ มีเส้นผ่านศูนย์กลาง: ${\displaystyle G}$${\displaystyle 3}$

${\displaystyle \alpha _{0}(G)\leq \chi _{\rho }(G)\leq \alpha _{0}(G)+1}$

สำหรับกราฟหลายส่วนสมบูรณ์และกราฟวงล้อ : ${\displaystyle G}$

${\displaystyle \chi _{\rho }(G)=\alpha _{0}(G)+1}$

สำหรับกราฟกริด : ^{[ 1 ] [ 4 ]}${\displaystyle r\times c}$${\displaystyle G_{r,c}}$

• ${\displaystyle \chi _{\rho }(G_{2,c})=5}$สำหรับ${\displaystyle c\geq 6}$
• ${\displaystyle \chi _{\rho }(G_{3,c})=7}$สำหรับ${\displaystyle c\geq 12}$
• ${\displaystyle \chi _{\rho }(G_{4,c})=8}$สำหรับ${\displaystyle c\geq 10}$
• ${\displaystyle \chi _{\rho }(G_{5,c})=9}$สำหรับ${\displaystyle c\geq 10}$
• ${\displaystyle \chi _{\rho }(G_{r,c})\leq 23}$สำหรับตารางกริดจำกัดใดๆ
• สำหรับ... ( กราฟตารางสี่เหลี่ยม ):${\displaystyle r=c=1,2,3,4}$

${\displaystyle \chi _{\rho }(G_{r,c})=1,3,4,5,7,8,9,9,10,11}$... (ลำดับA362580ในOEIS )

ตารางสี่เหลี่ยมจัตุรัส อนันต์มี: ^{[ 4 ]}${\displaystyle G_{\infty ,\infty }}$

${\displaystyle \chi _{\rho }(G_{\infty ,\infty })=15}$

โครงตาข่ายหก เหลี่ยมอนันต์มี: ^{[ 2 ]}${\displaystyle H}$

${\displaystyle \chi _{\rho }(H)=7}$

โครงตาข่ายสามเหลี่ยมอนันต์มีจำนวนสีบรรจุอนันต์^{[ 2 ]}

สำหรับกราฟย่อย ของกราฟซึ่งได้มาจากการแบ่งขอบแต่ละขอบออกหนึ่งครั้ง: ^{[ 5 ]}${\displaystyle S(G)}$${\displaystyle G}$

• สำหรับกราฟเชื่อมต่อ ที่มีจุดยอดอย่างน้อย 3 จุด:${\displaystyle G}$

${\displaystyle \omega (G)+1\leq \chi _{\rho }(S(G))\leq \chi _{\rho }(G)+1}$

• สำหรับกราฟสองส่วนที่เชื่อมต่อกันซึ่งมีขอบอย่างน้อยสองขอบ:

${\displaystyle \chi _{\rho }(S(G))=3}$

สำหรับผลคูณคาร์ทีเซียน ของกราฟที่เชื่อมต่อกันและมีจุดยอดอย่างน้อยสองจุด: ^{[ 5 ]}${\displaystyle G\square H}$${\displaystyle G}$${\displaystyle H}$

${\displaystyle \chi _{\rho }(G\square H)\geq (\chi _{\rho }(G)+1)|H|-{\text{diam}}(G\square H)(|H|-1)-1}$

สำหรับผลคูณคาร์ทีเซียนกับกราฟสมบูรณ์: ^{[ 5 ]}

${\displaystyle \chi _{\rho }(G\square K_{n})\geq n\chi _{\rho }(G)-(n-1){\text{diam}}(G)}$

กราฟเชื่อมต่อจะมีค่าก็ต่อเมื่อเป็นกราฟรูปดาว เท่านั้น${\displaystyle G}$${\displaystyle \chi _{\rho }(G)=2}$${\displaystyle G}$

กราฟจะมีก็ต่อเมื่อสามารถสร้างได้โดยการนำมัลติกราฟแบบสองส่วนมาแบ่งขอบทุกขอบออกเพียงครั้งเดียว เพิ่มใบให้กับจุดยอดบางจุด และดำเนินการบวกเพียงครั้งเดียวกับจุดยอดบางจุด^{[ 1 ]}${\displaystyle \chi _{\rho }(G)=3}$${\displaystyle T}$

แบบจำลองการระบายสีบรรจุภัณฑ์สำหรับปัญหาการจัดสรรความถี่ในการออกอากาศ ซึ่งสถานีวิทยุจะต้องได้รับการจัดสรรความถี่เพื่อให้สถานีที่มีความถี่เดียวกันอยู่ห่างกันมากพอที่จะหลีกเลี่ยงการรบกวน ข้อกำหนดระยะทางจะเพิ่มขึ้นตามกำลังของสัญญาณออกอากาศ^{[ 1 ]}

• การออกอากาศแบบครอบงำ : ฟังก์ชันที่(ความเยื้องศูนย์) และทุกจุดยอดที่มีจะมีเพื่อนบ้านที่มีและ${\displaystyle b:V\to \{0,1,\ldots \}}$${\displaystyle b(u)\leq e(u)}$${\displaystyle b(v)=0}$${\displaystyle u}$${\displaystyle b(u)>0}$${\displaystyle d(u,v)\leq b(u)}$
• ความเป็นอิสระในการออกอากาศ : การออกอากาศที่หมายความว่า${\displaystyle b(u),b(v)>0}$${\displaystyle d(u,v)>b(u)}$
• ${\displaystyle S}$-การระบายสีแบบแพ็ค (หรือ-การระบายสี ): สำหรับลำดับ จำนวนเต็มบวกที่ไม่ลดลง จุดยอดในชั้นสี ต้องอยู่ห่างกันมากกว่าการระบายสีแบบแพ็คมาตรฐานสอดคล้องกับจำนวนสีโครมาติกแบบ -แพ็คคือจำนวนสีขั้นต่ำที่ต้องการ^{[ 1 ] [ 2 ]}${\displaystyle (s_{1},s_{2},\ldots ,s_{k})}$${\displaystyle S=(s_{1},s_{2},\ldots )}$${\displaystyle i}$${\displaystyle s_{i}}$${\displaystyle S=(1,2,3,\ldots )}$${\displaystyle S}$${\displaystyle \chi _{S}(G)}$

• การระบายสีกราฟ
• รายการระบายสี
• การระบายสีแบบเศษส่วน
• การระบายสีแบบอะไซคลิก