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

• ไม่มีจุดยอดที่อยู่ติดกันสองจุดใดที่มีสีเดียวกัน และ
• จำนวนจุดยอดในกลุ่มสีสองกลุ่มใดๆ จะแตกต่างกันไม่เกินหนึ่งจุด

นั่นคือ การแบ่งจุดยอดระหว่างสีต่างๆ นั้นมีความสม่ำเสมอมากที่สุดเท่าที่จะเป็นไปได้ ตัวอย่างเช่น การให้สีที่แตกต่างกันแก่จุดยอดแต่ละจุดจะถือว่ายุติธรรม แต่โดยทั่วไปแล้วจะใช้สีมากกว่าที่จำเป็นในการระบายสีที่ยุติธรรมอย่างเหมาะสม วิธีที่เทียบเท่ากันในการกำหนดการระบายสีที่ยุติธรรมคือ การฝังกราฟที่กำหนดให้เป็นกราฟย่อยของกราฟ Turánที่มีชุดจุดยอดเดียวกัน มีจำนวนสี สองประเภท ที่เกี่ยวข้องกับการระบายสีที่ยุติธรรม^{[ 1 ]}จำนวนสีที่ยุติธรรมของกราฟGคือจำนวนk ที่เล็กที่สุด ที่ทำให้Gมีการระบายสีที่ยุติธรรมด้วยสีk สี แต่ Gอาจไม่มีการระบายสีที่ยุติธรรมสำหรับจำนวนสีที่มากกว่าบางจำนวนเกณฑ์สีที่ยุติธรรมของG คือ ^ค่า kที่เล็กที่สุดที่ทำให้Gมีการระบายสีที่ยุติธรรมสำหรับจำนวนสีใดๆ ที่มากกว่าหรือเท่ากับk ^{[ 2} ]

ทฤษฎีบทHajnal–Szemerédiซึ่งตั้งเป็นข้อสันนิษฐานโดยPaul Erdős  ( 1964 ) และได้รับการพิสูจน์โดยAndrás HajnalและEndre Szemerédi  ( 1970 ) ระบุว่ากราฟใดๆ ที่มีดีกรีสูงสุด Δ จะมีการระบายสีที่เท่าเทียมกันด้วยสี Δ + 1 สี ข้อสันนิษฐานที่เกี่ยวข้องหลายข้อยังคงเปิดอยู่ อัลกอริทึมเวลาพหุนามยังเป็นที่รู้จักสำหรับการค้นหาการระบายสีที่ตรงกับขอบเขตนี้^{[ 3 ]}และสำหรับการค้นหาการระบายสีที่เหมาะสมที่สุดของกราฟประเภทพิเศษ แต่ปัญหาทั่วไปของการตัดสินใจว่ากราฟใดๆ มีการระบายสีที่เท่าเทียมกันด้วยจำนวนสีที่กำหนดหรือไม่นั้นเป็นปัญหา NP-complete

กราฟ รูปดาวK _1,5ซึ่งมีจุดยอดกลางเพียงจุดเดียวเชื่อมต่อกับจุดยอดอื่นอีกห้าจุด เป็นกราฟ สอง ส่วนสมบูรณ์ดังนั้นจึงสามารถระบายสีได้ด้วยสองสี อย่างไรก็ตาม การระบายสีที่ได้จะมีจุดยอดหนึ่งจุดอยู่ในกลุ่มสีหนึ่ง และห้าจุดอยู่ในกลุ่มสีอื่น จึงไม่ยุติธรรม จำนวนสีที่น้อยที่สุดในการระบายสีกราฟนี้อย่างยุติธรรมคือสี่สี: จุดยอดกลางต้องเป็นจุดยอดเพียงจุดเดียวในกลุ่มสีนั้น ดังนั้นจุดยอดอีกห้าจุดจะต้องถูกแบ่งออกเป็นอย่างน้อยสามกลุ่มสี เพื่อให้แน่ใจว่ากลุ่มสีอื่นๆ แต่ละกลุ่มมีจุดยอดไม่เกินสองจุด

โดยทั่วไปแล้วMeyer (1973)สังเกตว่ากราฟรูปดาวK _{1, n} ใดๆ ก็ตาม ต้องการสีในการระบายสีแบบยุติธรรม ดังนั้น จำนวนสีของกราฟอาจแตกต่างจากจำนวนสีในการระบายสีแบบยุติธรรมได้มากถึงn /4 เท่า เนื่องจากK _1,5มีดีกรีสูงสุดห้า จำนวนสีที่รับประกันโดยทฤษฎีบท Hajnal–Szemerédi จึงเป็นหกสี ซึ่งได้มาจากการกำหนดสีที่แตกต่างกันให้กับแต่ละจุดยอด ${\displaystyle \scriptstyle 1+\lceil n/2\rceil }$

ปรากฏการณ์ที่น่าสนใจอีกอย่างหนึ่งพบได้ในกราฟสองส่วนสมบูรณ์อีกแบบหนึ่ง คือK _{2 n  + 1,2 n  + 1}กราฟนี้มีการระบายสีแบบ 2 สีที่เท่าเทียมกัน ซึ่งกำหนดโดยการแบ่งสองส่วนของกราฟ อย่างไรก็ตาม มันไม่มีการระบายสีแบบ (2 n  + 1) สีที่เท่าเทียมกัน: การแบ่งจุดยอดอย่างเท่าเทียมกันออกเป็นกลุ่มสีจำนวนนั้นจะต้องมีจุดยอดสองจุดต่อกลุ่มพอดี แต่ด้านทั้งสองของการแบ่งสองส่วนไม่สามารถแบ่งออกเป็นคู่ได้ เพราะแต่ละด้านมีจำนวนจุดยอดเป็นเลขคี่ ดังนั้น ค่าเกณฑ์สีที่เท่าเทียมกันของกราฟนี้จึงเป็น 2 n  + 2 ซึ่งมากกว่าจำนวนสีที่เท่าเทียมกันซึ่งก็คือสองอย่างมาก

ทฤษฎีบทของบรูคส์กล่าวว่า กราฟเชื่อมต่อใดๆ ที่มีดีกรีสูงสุด Δ จะมีการระบายสีแบบ Δ โดยมีข้อยกเว้นสองประการ ( กราฟสมบูรณ์และวงจรคี่) อย่างไรก็ตาม การระบายสีนี้โดยทั่วไปอาจไม่ยุติธรรม พอล เออร์โดส  ( 1964 ) ตั้งข้อสันนิษฐานว่า การระบายสีที่ยุติธรรมนั้นเป็นไปได้โดยใช้สีเพิ่มอีกเพียงสีเดียว: กราฟใดๆ ที่มีดีกรีสูงสุด Δ จะมีการระบายสีที่ยุติธรรมด้วยสี Δ + 1 สี กรณี Δ = 2 นั้นตรงไปตรงมา (การรวมกันของเส้นทางและวงจรใดๆ สามารถระบายสีได้อย่างยุติธรรมโดยใช้รูปแบบซ้ำๆ ของสามสี โดยมีการปรับเปลี่ยนเล็กน้อยในการทำซ้ำเมื่อปิดวงจร) และกรณี Δ + 1 =  n /3 นั้นได้รับการแก้ไขแล้วโดยคอร์ราดีและฮัจนาล (1963)ข้อสันนิษฐานทั้งหมดได้รับการพิสูจน์โดยฮัจนาลและเซเมเรดี (1970)และปัจจุบันรู้จักกันในชื่อทฤษฎีบทฮัจนาล-เซเมเรดี การพิสูจน์ดั้งเดิมของพวกเขายาวและซับซ้อนKierstead & Kostochka (2008)ได้ให้บทพิสูจน์ที่ง่ายกว่า พวกเขาได้อธิบายอัลกอริทึมแบบใช้เวลาพหุนามสำหรับการหาการระบายสีที่เท่าเทียมกันด้วยจำนวนสีดังกล่าว โดยให้เครดิตแก่ Marcelo Mydlarz และ Endre Szemerédi สำหรับอัลกอริทึมแบบใช้เวลาพหุนามที่ยังไม่ได้ตีพิมพ์ก่อนหน้านี้ นอกจากนี้ Kierstead และ Kostochka ยังประกาศแต่ไม่ได้พิสูจน์การเสริมความแข็งแกร่งของทฤษฎีบท เพื่อแสดงให้เห็นว่า การระบายสี k+1 ที่เท่าเทียมกัน นั้นมีอยู่จริงเมื่อใดก็ตามที่จุดยอดที่อยู่ติดกันสองจุดทุกจุดมีผลรวมของดีกรีไม่เกิน 2k +  1

Meyer (1973)ตั้งข้อสันนิษฐานเกี่ยวกับทฤษฎีบทของ Brooks ในรูปแบบหนึ่งสำหรับการระบายสีอย่างเท่าเทียมกัน: กราฟเชื่อมต่อทุกกราฟที่มีดีกรีสูงสุด Δ จะมีการระบายสีอย่างเท่าเทียมกันด้วยสี Δ หรือน้อยกว่า ยกเว้นกราฟสมบูรณ์และวัฏจักรคี่ ข้อสันนิษฐานฉบับปรับปรุงระบุว่ากราฟดังกล่าวทุกกราฟจะมีการระบายสีอย่างเท่าเทียมกันด้วยสี Δ พอดี โดยมีข้อยกเว้นเพิ่มเติมคือกราฟสองส่วนสมบูรณ์ซึ่งทั้งสองด้านของการแบ่งสองส่วนมีจำนวนจุดยอดคี่เท่ากัน^{[ 1 ]}

เซย์มัวร์ (1974)เสนอการเสริมความแข็งแกร่งของทฤษฎีบทฮัจนาล-เซเมอเรดี ซึ่งครอบคลุมทฤษฎีบทของดิแรก ที่ว่า กราฟหนาแน่นเป็น กราฟ แฮมิลโทเนียน ด้วย โดยเขาตั้งข้อสันนิษฐานว่า ถ้าทุกจุดยอดใน กราฟ nจุดยอดมีเพื่อนบ้านอย่างน้อยkn /( k  + 1) จุด กราฟนั้นจะมีกราฟย่อยที่เกิดจากการเชื่อมต่อจุดยอดที่อยู่ห่างกันไม่เกินkขั้นใน วัฏจักร nจุด กรณีที่k  = 1 คือทฤษฎีบทของดิแรกนั่นเอง ทฤษฎีบทฮัจนาล-เซเมอเรดีอาจได้มาจากข้อสันนิษฐานนี้โดยการใช้ข้อสันนิษฐานกับค่าk ที่มากขึ้น กับกราฟส่วนเติมเต็มของกราฟที่กำหนด และใช้ลำดับย่อยที่ต่อเนื่องกันของจุดยอดจาก วัฏจักร n จุดเป็นชั้นสี ข้อสันนิษฐานของเซย์มัวร์ได้รับการพิสูจน์โดยประมาณแล้ว กล่าวคือ สำหรับกราฟที่ทุกจุดยอดมี เพื่อนบ้านอย่างน้อยkn /( k  + 1)+o( n ) จุด ^{[ 4 ]}การพิสูจน์ใช้เครื่องมือเชิงลึกหลายอย่างรวมถึงทฤษฎีบท Hajnal–Szemerédi เอง

ทฤษฎีบท Hajnal–Szemerédi ยังมีการสรุปทั่วไปอีกประการหนึ่งคือ ข้อสันนิษฐานของ Bollobás–Eldridge–Catlin (หรือเรียกสั้นๆ ว่า ข้อสันนิษฐาน BEC) ^{[ 5 ]}ข้อสันนิษฐานนี้ระบุว่า ถ้าG ₁และG ₂เป็นกราฟบน จุดยอด nจุด โดยมีดีกรีสูงสุด Δ ₁และ Δ ₂ตามลำดับ และถ้า (Δ ₁  + 1)(Δ ₂  + 1) ≤  n+1แล้วG ₁และG ₂สามารถบรรจุได้ นั่นคือG ₁และG ₂สามารถแสดงบนเซตของ จุดยอด nจุดเดียวกันโดยไม่มีขอบร่วมกัน ทฤษฎีบท Hajnal–Szemerédi เป็นกรณีพิเศษของข้อสันนิษฐานนี้ ซึ่งG ₂ เป็นการรวม กันแบบไม่ทับซ้อนของคลิกCatlin (1974)ให้เงื่อนไขที่คล้ายกันแต่เข้มงวดกว่าสำหรับ Δ ₁และ Δ ₂ซึ่งรับประกันได้ว่าการบรรจุดังกล่าวมีอยู่จริง

สำหรับต้นไม้ใดๆ ที่มีระดับสูงสุด Δ จำนวนสีที่สมดุลจะมีค่าไม่เกิน

${\displaystyle 1+\lceil \เดลต้า /2\rceil }$^{[ 6 ]}

โดยกรณีที่เลวร้ายที่สุดเกิดขึ้นกับดาว อย่างไรก็ตาม ต้นไม้ส่วนใหญ่มีจำนวนสีที่เท่ากันอย่างมีนัยสำคัญน้อยกว่า: หากต้นไม้ที่มีnจุดยอดมี Δ ≤  n /3 − O(1) แสดงว่ามีการระบายสีที่เท่ากันโดยใช้เพียงสามสี^{[ 7 ]} Furmańczyk (2006)ศึกษาจำนวนสีที่เท่ากันของ ผล คูณ กราฟ

ปัญหาการหาการระบายสีที่เป็นธรรมโดยใช้สีให้น้อยที่สุดเท่าที่จะเป็นไปได้ (ต่ำกว่าขอบเขต Hajnal-Szemerédi) ก็ได้รับการศึกษาเช่นกัน การลดรูปโดยตรงจากการระบายสีกราฟไปสู่การระบายสีที่เป็นธรรมสามารถพิสูจน์ได้โดยการเพิ่มจุดยอดที่แยกเดี่ยวจำนวนมากพอลงในกราฟ ซึ่งแสดงให้เห็นว่าการทดสอบว่ากราฟมีการระบายสีที่เป็นธรรมด้วยจำนวนสีที่กำหนด (มากกว่าสอง) หรือไม่นั้น เป็นปัญหา NP-complete อย่างไรก็ตาม ปัญหานี้จะน่าสนใจมากขึ้นเมื่อจำกัดเฉพาะกราฟประเภทพิเศษหรือจากมุมมองของความซับซ้อน แบบพารามิเตอร์Bodlaender & Fomin (2005)แสดงให้เห็นว่า เมื่อกำหนดกราฟGและจำนวนสีc แล้ว เป็นไปได้ที่จะทดสอบว่า Gยอมรับการ ระบายสี c ที่เป็นธรรมหรือไม่ ในเวลา O( n ^{O( t )} ) โดยที่tคือtreewidthของGโดยเฉพาะอย่างยิ่ง การระบายสีที่เป็นธรรมสามารถแก้ไขได้อย่างเหมาะสมในเวลาพหุนามสำหรับต้นไม้ (ซึ่งเป็นที่รู้จักมาก่อนโดยChen & Lih 1994 ) และกราฟระนาบนอก อัลกอริทึมเวลาพหุนามยังเป็นที่รู้จักสำหรับการระบายสีกราฟแยกอย่างเท่าเทียมกัน[ 8 ^{]อย่างไรก็ตามFellows} et al. (2007)พิสูจน์ว่าเมื่อ treewidth เป็นพารามิเตอร์ของอัลกอริทึม ปัญหาจะเป็น W[1]-hard ดังนั้นจึงไม่น่าเป็นไปได้ที่จะมีอัลกอริทึมเวลาพหุนามที่ไม่ขึ้นอยู่กับพารามิเตอร์นี้ หรือแม้กระทั่งการพึ่งพาพารามิเตอร์อาจถูกย้ายออกจากเลขชี้กำลังในสูตรสำหรับเวลาการทำงาน

แรงจูงใจประการหนึ่งสำหรับการระบายสีอย่างเท่าเทียมกันที่เสนอโดยMeyer (1973)เกี่ยวข้องกับ ปัญหา การจัดตารางเวลาในการประยุกต์ใช้ดังกล่าว จุดยอดของกราฟแสดงถึงชุดของงานที่จะต้องทำ และขอบเชื่อมต่องานสองงานที่ไม่ควรทำพร้อมกัน การระบายสีกราฟนี้แสดงถึงการแบ่งงานออกเป็นกลุ่มย่อยที่อาจทำพร้อมกันได้ ดังนั้น จำนวนสีในการระบายสีจึงสอดคล้องกับจำนวนขั้นตอนเวลาที่จำเป็นในการทำงานทั้งหมด เนื่องจาก การพิจารณา เรื่องการกระจายภาระงาน จึง เป็นที่พึงปรารถนาที่จะทำงานจำนวนเท่ากันหรือเกือบเท่ากันในแต่ละขั้นตอนเวลา และการกระจายภาระงานนี้คือสิ่งที่การระบายสีอย่างเท่าเทียมกันบรรลุผลFurmańczyk (2006)กล่าวถึงการประยุกต์ใช้เฉพาะของปัญหาการจัดตารางเวลาประเภทนี้ คือ การจัดสรรหลักสูตรมหาวิทยาลัยให้กับช่วงเวลาต่างๆ ในลักษณะที่กระจายหลักสูตรอย่างเท่าเทียมกันในช่วงเวลาที่มีอยู่ และหลีกเลี่ยงการจัดตารางหลักสูตรที่ไม่เข้ากันในเวลาเดียวกัน

ทฤษฎีบท Hajnal-Szemerédi ยังถูกนำมาใช้เพื่อจำกัดขอบเขตความแปรปรวนของผลรวมของตัวแปรสุ่มที่มีความสัมพันธ์จำกัด ( Pemmaraju 2001 ; Janson & Ruciński 2002 ) หาก (เช่นเดียวกับการตั้งค่าสำหรับบทพิสูจน์ย่อยเฉพาะที่ของ Lovász ) ตัวแปรแต่ละตัวขึ้นอยู่กับตัวแปรอื่นไม่เกิน Δ ตัว การระบายสีอย่างเท่าเทียมกันของกราฟความสัมพันธ์อาจถูกนำมาใช้เพื่อแบ่งตัวแปรออกเป็นเซตย่อยอิสระ ซึ่ง สามารถคำนวณ ขอบเขต Chernoffได้ ส่งผลให้ขอบเขตโดยรวมของความแปรปรวนแคบลงกว่าการแบ่งแบบที่ไม่เท่าเทียมกัน

• ECOPT คืออัลกอริทึมแบบ Branch and Cut สำหรับแก้ปัญหาการระบายสีอย่างเท่าเทียมกัน