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

การระบายสีที่ไม่สมบูรณ์ได้รับการแนะนำเกือบพร้อมกันโดย Andrews และ Jacobson ^{[ 1 ]} Harary และ Jones และ Cowen, Cowen และ Woodall ^{[ 2 ]}การสำรวจเกี่ยวกับการระบายสีนี้และการระบายสีที่เกี่ยวข้องได้รับการนำเสนอโดย Marietjie Frick ^{[ 3 ]} Cowen, Cowen และ Woodall ^{[ 2 ]}มุ่งเน้นไปที่กราฟที่ฝังอยู่บนพื้นผิวและให้ลักษณะที่สมบูรณ์ของkและd ทั้งหมด ที่ทำให้กราฟระนาบทุกกราฟสามารถระบายสีได้แบบ ( k ​​, d ) กล่าวคือ ไม่มีdที่ทำให้กราฟระนาบทุกกราฟสามารถระบายสีได้แบบ (1, d ) หรือ (2, d ) มีกราฟระนาบที่ไม่สามารถระบายสีได้แบบ (3, 1) แต่กราฟระนาบทุกกราฟสามารถระบายสีได้แบบ (3, 2) เมื่อรวมกับการระบายสีแบบ (4, 0) ที่ได้จากทฤษฎีบทสี่สีสิ่งนี้จะแก้ปัญหาจำนวนสีที่ไม่สมบูรณ์สำหรับระนาบ Poh ^{[ 4 ]}และ Goddard ^{[ 5 ]}แสดงให้เห็นว่ากราฟระนาบใดๆ มีการระบายสีพิเศษแบบ (3,2) ซึ่งแต่ละคลาสสีเป็นป่าเชิงเส้นและสามารถได้รับผลลัพธ์ทั่วไปมากขึ้นจาก Woodall สำหรับพื้นผิวทั่วไป แสดงให้เห็นว่าสำหรับแต่ละจีนัสจะมีอยู่เช่นนั้นที่กราฟทุกกราฟบนพื้นผิวของจีนัสสามารถระบายสีแบบ(4, k ) ได้ ^{[ 2 ]}สิ่งนี้ได้รับการปรับปรุงให้สามารถระบายสีแบบ (3, k ) ได้โดยDan Archdeacon [ ^{6 ] สำหรับ} กราฟทั่วไป ผลลัพธ์ของLászló Lovászจากช่วงปี 1960 ซึ่งได้รับการค้นพบใหม่หลายครั้ง^{[ 7 ] [ 8 ] [ 9 ]}ให้ ขั้นตอนวิธีเวลา O(∆E)สำหรับการระบายสีกราฟที่มีข้อบกพร่องที่มีดีกรีสูงสุด ∆ ${\displaystyle g\geq 0}$${\displaystyle k=k(g)}$${\displaystyle g}$

การระบายสี แบบ ( k ,  d ) ของกราฟGคือการระบายสีจุดยอดด้วย สี kสี โดยที่จุดยอดv แต่ละจุดจะมี เพื่อนบ้านที่มีสีเดียวกับจุดยอดvไม่เกินd จุด เราถือว่าkเป็นจำนวนเต็มบวก (ไม่จำเป็นต้องพิจารณากรณีที่k = 0) และdเป็นจำนวนเต็มที่ไม่เป็นลบ ดังนั้น การระบายสีแบบ ( k , 0) จึงเทียบเท่ากับการระบายสีจุดยอดที่เหมาะสม^{[ 10 ]}

จำนวนสีขั้นต่ำkที่จำเป็นสำหรับG ที่ ^{สามารถ} ระบายสีได้ ( k , d ) เรียกว่าจำนวนสีd ที่บกพร่อง [ ^{11 ]}${\displaystyle \chi _{d}(G)}$

สำหรับกราฟคลาสGจำนวนสีที่ขาดหายไปของGคือจำนวนเต็มk ที่น้อยที่สุด ซึ่งสำหรับจำนวนเต็มd บางตัว กราฟทุกกราฟในG สามารถระบายสีได้ด้วยสี ( k , d ) ตัวอย่างเช่น จำนวนสีที่ขาดหายไปของคลาสกราฟระนาบเท่ากับ 3 เนื่องจากกราฟระนาบทุกกราฟสามารถระบายสีได้ด้วยสี (3, 2) และสำหรับจำนวนเต็มd บางตัว จะมีกราฟระนาบที่ไม่สามารถระบายสีได้ด้วยสี (2, d )

ให้cเป็นการระบายสีจุดยอดของกราฟGความไม่เหมาะสมของจุดยอดvของGเมื่อเทียบกับการระบายสีcคือจำนวนเพื่อนบ้านของvที่มีสีเดียวกับvถ้าความไม่เหมาะสมของvเป็น 0 แล้วvจะถูกเรียกว่าถูกระบายสีอย่างเหมาะสม^{[ 2 ]}

ให้cเป็นการระบายสีจุดยอดของกราฟGความไม่เหมาะสมของcคือค่าสูงสุดของความไม่เหมาะสมของจุดยอดทั้งหมดของGดังนั้น ความไม่เหมาะสมของการระบายสีจุดยอดที่เหมาะสมคือ 0 ^{[ 2 ]}

ตัวอย่างของการระบายสีที่ไม่ถูกต้องของวงกลมที่มีห้าจุดยอด แสดงดังในรูป รูปย่อยแรกเป็นตัวอย่างของการระบายสีจุดยอดที่ถูกต้องหรือการระบายสีแบบ ( k , 0) รูปย่อยที่สองเป็นตัวอย่างของการระบายสีแบบ ( k , 1) และรูปย่อยที่สามเป็นตัวอย่างของการระบายสีแบบ ( k , 2) โปรดสังเกตว่า ${\displaystyle C_{5}}$

${\displaystyle \chi _{0}(C_{5})=\chi (C_{5})=3}$

${\displaystyle \chi _{1}(C_{5})=3}$

${\displaystyle \chi _{2}(C_{n})=1;\forall n\in \mathbb {N} }$

• การพิจารณากราฟที่เชื่อมต่อกันก็เพียงพอแล้ว เนื่องจากกราฟG สามารถระบายสีด้วยสี ( k , d ) ได้ก็ต่อเมื่อส่วนประกอบที่เชื่อมต่อกัน ทุกส่วน ของG สามารถระบายสีด้วยสี ( k , d ) ได้^{[ 2 ]}
• ^{ในแง่ ของ}ทฤษฎีกราฟ แต่ละคลาสสีในการระบายสีจุดยอดที่เหมาะสมจะสร้างเซตอิสระในขณะที่แต่ละคลาสสีในการระบายสีที่ไม่สมบูรณ์จะสร้างกราฟย่อยที่มีดีกรีไม่เกินd ^[ 12 ^]
• ถ้ากราฟสามารถระบายสีได้แบบ ( k , d ) แล้วกราฟนั้นก็สามารถระบายสีได้แบบ ( ^k ′ , d′ ) สำหรับแต่ละคู่ ( k′ , d′ ) โดยที่k′ ≥ kและd′ ≥ d ^{[ 2} ]

บทพิสูจน์:ให้ G เป็นกราฟระนาบนอกที่เชื่อมต่อกัน ให้ n เป็นจุดยอดใดๆ ของG ให้ n เป็นเซตของจุดยอดของ G ที่อยู่ห่าง จาก n เป็นระยะทางn ให้ n เป็นกราฟย่อยที่เกิดจากn สมมติว่า n มีจุดยอดที่มีดีกรี 3 หรือมากกว่านั้น แล้ว n จะมี n เป็นกราฟย่อย จากนั้นเรายุบขอบทั้งหมดของ n เพื่อให้ได้กราฟใหม่ ${\displaystyle G}$${\displaystyle v_{0}}$${\displaystyle G}$${\displaystyle V_{i}}$${\displaystyle G}$${\displaystyle i}$${\displaystyle v_{0}}$${\displaystyle G_{i}}$${\displaystyle \langle V_{i}\rangle }$${\displaystyle V_{i}}$${\displaystyle G_{i}}$${\displaystyle K_{1,3}}$${\displaystyle V_{0}\ถ้วย V_{1}\ถ้วย ...\ถ้วย V_{i-1}}$${\displaystyle G'}$

${\displaystyle \langle V_{0}\cup V_{1}\cup ...\cup V_{i-1}\rangle }$ของเชื่อมต่อกันเนื่องจากทุกจุดยอดในอยู่ติดกับจุดยอดในดังนั้น โดยการยุบขอบทั้งหมดที่กล่าวมาข้างต้น เราจะได้เช่นนั้น กราฟย่อยของจะถูกแทนที่ด้วยจุดยอดเดียวที่อยู่ติดกับทุกจุดยอดในดังนั้นจึงมีเป็นกราฟย่อย แต่กราฟย่อยทุกกราฟของกราฟนอกระนาบเป็นกราฟนอกระนาบ และกราฟทุกกราฟที่ได้จากการยุบขอบของกราฟนอกระนาบเป็นกราฟนอกระนาบ ซึ่งหมายความว่าเป็นกราฟนอกระนาบ ซึ่งขัดแย้งกัน ดังนั้นไม่มีกราฟใดที่มีจุดยอดที่มีดีกรี 3 หรือมากกว่า ซึ่งหมายความว่า สามารถระบายสีแบบ ( k , 2) ได้ ไม่มีจุดยอดของที่อยู่ติดกับจุดยอดใด ๆ ของหรือดังนั้นจุดยอดของสามารถระบายสีน้ำเงินได้ถ้าเป็นเลขคี่และสีแดงถ้าเป็นเลขคู่ ดังนั้น เราจึงสร้างการระบายสีแบบ (2,2) ของ^{[ 2 ]}${\displaystyle G'}$${\displaystyle V_{i}}$${\displaystyle V_{i-1}}$${\displaystyle G'}$${\displaystyle \langle V_{0}\cup V_{1}\cup ...\cup V_{i-1}\rangle }$${\displaystyle G'}$${\displaystyle V_{i}}$${\displaystyle G'}$${\displaystyle K_{2,3}}$${\displaystyle K_{2,3}}$${\displaystyle G_{i}}$${\displaystyle G}$${\displaystyle V_{i}}$${\displaystyle V_{i-1}}$${\displaystyle V_{i+1},i\geqslant 1}$${\displaystyle V_{i}}$${\displaystyle i}$${\displaystyle G}$

บทสรุป: กราฟระนาบทุกกราฟสามารถระบายสีแบบ (4,2) ได้ เนื่องจากถ้ากราฟระนาบทุกกราฟ(เช่นเดียวกับข้างต้น) จะเป็นกราฟระนาบนอก ดังนั้นกราฟทุกกราฟจึงสามารถระบายสีแบบ (2,2) ได้ ด้วยเหตุนี้ จุดยอดแต่ละจุดของกราฟจึงสามารถระบายสีน้ำเงินหรือสีแดงได้ถ้าจำนวนจุดยอดเป็นเลขคู่ และสีเขียวหรือสีเหลืองได้ถ้า จำนวนจุดยอดเป็นเลขคี่ จึงทำให้ กราฟ มีสีแบบ (4,2)${\displaystyle G}$${\displaystyle G_{i}}$${\displaystyle G_{i}}$${\displaystyle V_{i}}$${\displaystyle i}$${\displaystyle i}$${\displaystyle G}$

สำหรับจำนวนเต็มทุกจำนวนจะมีจำนวนเต็มหนึ่งที่ทำให้กราฟทุกกราฟที่ไม่มีไมเนอร์สามารถระบายสีได้^{[ 13 ]}${\displaystyle t}$${\displaystyle N}$${\displaystyle G}$${\displaystyle K_{t}}$${\displaystyle (t-1,N)}$

การระบายสีที่บกพร่องนั้นยากต่อการคำนวณ การตัดสินว่ากราฟที่กำหนดยอมรับการระบายสีแบบ (3,1) หรือไม่นั้นเป็นปัญหา NP-complete แม้ในกรณีที่ กราฟ นั้นมีดีกรีของจุดยอดสูงสุด 6 หรือเป็นกราฟระนาบที่มีดีกรีของจุดยอดสูงสุด 7 ก็ตาม^{[ 14 ]}${\displaystyle G}$${\displaystyle G}$

ตัวอย่างหนึ่งของการประยุกต์ใช้การระบายสีที่บกพร่องคือปัญหาการจัดตารางเวลา โดยที่จุดยอดแทนงาน (เช่น ผู้ใช้ในระบบคอมพิวเตอร์) และขอบแทนความขัดแย้ง (จำเป็นต้องเข้าถึงไฟล์เดียวกันตั้งแต่หนึ่งไฟล์ขึ้นไป) การอนุญาตให้มีข้อบกพร่องหมายถึงการยอมรับความขัดแย้งในระดับหนึ่ง: ผู้ใช้แต่ละคนอาจพบว่าความล่าช้าสูงสุดที่เกิดขึ้นจากการดึงข้อมูลเมื่อมีผู้ใช้อื่นอีกสองรายที่มีความขัดแย้งในระบบนั้นเป็นที่ยอมรับได้ และหากมีมากกว่าสองรายนั้นยอมรับไม่ได้^{[ 15 ]}