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

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

ธรรมเนียมการใช้สีมีที่มาจากวิธีการระบายสีประเทศในแผนที่การเมืองซึ่งแต่ละด้านของแผนที่จะถูกระบายสีอย่างแท้จริง ต่อมาได้มีการขยายแนวคิดนี้ไปสู่การระบายสีด้านของกราฟที่ฝังอยู่ในระนาบ โดยอาศัยหลักการทวิภาวะของระนาบ จึงกลายเป็นการระบายสีจุดยอด และในรูปแบบนี้สามารถขยายไปใช้กับกราฟทุกประเภทได้ ในการแสดงผลทางคณิตศาสตร์และคอมพิวเตอร์ มักจะใช้จำนวนเต็มบวกหรือจำนวนเต็มที่ไม่เป็นลบไม่กี่จำนวนแรกเป็น "สี" โดยทั่วไปแล้ว เราสามารถใช้เซตจำกัด ใดๆ ก็ได้ เป็น "เซตสี" ลักษณะของปัญหาการระบายสีขึ้นอยู่กับจำนวนสี แต่ไม่ขึ้นอยู่กับว่าสีเหล่านั้นคืออะไร

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

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

ในปี ค.ศ. 1890 เพอร์ซี จอห์น ฮีวูดชี้ให้เห็นว่าข้อโต้แย้งของเคมป์นั้นผิด อย่างไรก็ตาม ในบทความนั้น เขาได้พิสูจน์ทฤษฎีบทห้าสีโดยกล่าวว่าแผนที่ระนาบทุกแผ่นสามารถระบายสีได้ไม่เกินห้าสี โดยใช้แนวคิดของเคมป์ ในศตวรรษต่อมา มีการทำงานและการพัฒนาทฤษฎีมากมายเพื่อลดจำนวนสีเหลือสี่สี จนกระทั่งในที่สุดทฤษฎีบทสี่สีก็ได้รับการพิสูจน์ในปี ค.ศ. 1976 โดยเคนเนธ แอปเปลและวูล์ฟกัง ฮาเคนการพิสูจน์นั้นย้อนกลับไปสู่แนวคิดของฮีวูดและเคมป์ และละเลยการพัฒนาที่เกิดขึ้นในช่วงระหว่างนั้นเป็นอย่างมาก^{[ 3 ]}การพิสูจน์ทฤษฎีบทสี่สีนั้นน่าสนใจ นอกเหนือจากการแก้ปัญหาที่มีมานานนับศตวรรษแล้ว ยังเป็นการพิสูจน์โดยใช้คอมพิวเตอร์ช่วย ครั้งแรกที่สำคัญอีก ด้วย

ในปี พ.ศ. 2455 George David Birkhoffได้นำพหุนามสี มาใช้ ในการศึกษาปัญหาการระบายสี ซึ่งต่อมาได้รับการขยายเป็นพหุนาม TutteโดยWT Tutteซึ่งทั้งสองอย่างนี้เป็นตัวแปรสำคัญในทฤษฎีกราฟเชิงพีชคณิต Kempe ได้ให้ความสนใจกับกรณีทั่วไปที่ไม่ใช่ระนาบในปี พ.ศ. 2422 ^{[ 4 ]}และผลลัพธ์มากมายเกี่ยวกับการขยายการระบายสีกราฟระนาบไปยังพื้นผิวที่มีลำดับสูงกว่าก็เกิดขึ้นในช่วงต้นศตวรรษที่ 20

ในปี 1960 Claude Bergeได้ตั้งข้อสันนิษฐานอีกข้อหนึ่งเกี่ยวกับการระบายสีกราฟ นั่นคือข้อสันนิษฐานกราฟสมบูรณ์แบบที่แข็งแกร่ง (strong perfect graph conjecture ) ซึ่งเดิมทีได้รับแรงบันดาลใจจาก แนวคิด ทางทฤษฎีสารสนเทศที่เรียกว่า ความจุเป็นศูนย์ของข้อผิดพลาดของกราฟ (zero-error capacity of the graph) ที่ Shannonนำเสนอข้อสันนิษฐานนี้ยังคงไม่ได้รับการแก้ไขเป็นเวลา 40 ปี จนกระทั่งได้รับการพิสูจน์เป็นทฤษฎีกราฟสมบูรณ์แบบที่แข็งแกร่งอัน โด่งดัง โดยChudnovsky , Robertson , SeymourและThomasในปี 2002

การระบายสีกราฟได้รับการศึกษาในฐานะปัญหาเชิงอัลกอริทึมมาตั้งแต่ต้นทศวรรษ 1970: ปัญหาจำนวนสี (ดูหัวข้อ§ การระบายสีจุดยอดด้านล่าง) เป็นหนึ่งใน21 ปัญหา NP-complete ของ Karpจากปี 1972 และในเวลาเดียวกันนั้นเอง ก็มีการพัฒนาอัลกอริทึมแบบเวลาเลขชี้กำลังต่างๆ ขึ้นโดยอาศัยการย้อนกลับ (backtracking) และความสัมพันธ์เวียนเกิดแบบการลบและการหดตัว (deletion-contraction recurrence) ของZykov (1949)หนึ่งในแอปพลิเคชันหลักของการระบายสีกราฟ คือการจัดสรรรีจิสเตอร์ในคอมไพเลอร์ ซึ่งเปิดตัวในปี 1981

เมื่อใช้คำว่า "การระบายสีกราฟ" โดยไม่มีคำอธิบายเพิ่มเติม มักหมายถึงการระบายสีจุดยอดอย่างถูกต้อง กล่าวคือ การกำหนดสีให้กับจุดยอดของกราฟโดยที่ไม่มีจุดยอดสองจุดใดที่ใช้ขอบ เดียวกัน มีสีเดียวกัน เนื่องจากจุดยอดที่มีวงวน (เช่น การเชื่อมต่อกลับมายังจุดยอดนั้นโดยตรง) ไม่สามารถระบายสีได้อย่างถูกต้อง ดังนั้นจึงเข้าใจได้ว่ากราฟในบริบทนี้ไม่มีวงวน

ศัพท์เฉพาะของการใช้สีสำหรับป้ายกำกับจุดยอดนั้นมีที่มาจากระบบการระบายสีแผนที่ ป้ายกำกับเช่นสีแดงและสีน้ำเงินจะใช้เฉพาะเมื่อจำนวนสีมีน้อย และโดยปกติแล้วจะเข้าใจกันว่าป้ายกำกับเหล่านั้นถูกเลือกมาจากจำนวนเต็ม{1, 2, 3, ... }

การระบายสีโดยใช้สีไม่เกินkสี เรียกว่าการระบายสีk สี ( แบบเหมาะสม) จำนวนสีน้อยที่สุดที่จำเป็นในการระบายสีกราฟGเรียกว่าจำนวนสีโครมาติกและมักจะใช้สัญลักษณ์χ( G ) ^{[ 5 ]}บางครั้งใช้γ( G ) เนื่องจาก χ( G )ยังใช้เพื่อแสดงลักษณะเฉพาะของออยเลอร์ของกราฟด้วย^{[ 6 ]}กราฟที่สามารถกำหนดการระบายสีk สี (แบบเหมาะสม) ได้ เรียกว่า กราฟที่ สามารถระบายสีk สีได้ และเรียก ว่า กราฟ โครมาติกk สี ถ้าจำนวนสีโครมาติกของ กราฟเท่ากับ k พอดี เซตย่อยของจุดยอดที่กำหนดสีเดียวกันเรียกว่าคลาสสีแต่ละคลาสดังกล่าวเป็นเซตอิสระดังนั้น การระบายสี kสี จึงเหมือนกับการแบ่งเซตจุดยอดออกเป็นkเซตอิสระ และคำว่าk -partiteและk -colorableมีความหมายเหมือนกัน

พหุนามสี ( Chromatic Polynomial)นับจำนวนวิธีที่สามารถระบายสีกราฟโดยใช้สีบางส่วนจากจำนวนสีที่กำหนด ตัวอย่างเช่น หากใช้สามสี กราฟในภาพด้านข้างสามารถระบายสีได้ 12 วิธี หากใช้เพียงสองสี จะไม่สามารถระบายสีได้เลย หากใช้สี่สี สามารถระบายสีได้ 2⁴ + 4 × 12 = 72 วิธี: หากใช้ทั้งสี่สี จะมี 4! = 24 วิธีที่ถูกต้อง ( การกำหนดสี่สีให้กับ กราฟ 4 จุดยอด ใดๆถือเป็นการระบายสีที่ถูกต้อง) และสำหรับการเลือกใช้สามสีจากสี่สี จะมี 12 วิธีที่ถูกต้อง ดังนั้น สำหรับกราฟในตัวอย่าง ตารางแสดงจำนวนวิธีระบายสีที่ถูกต้องจะเริ่มต้นดังนี้:

พหุนามสี (Chromatic Polynomial) คือฟังก์ชันP ( G , t )ที่นับจำนวน การระบายสี t ครั้งของกราฟ Gดังที่ชื่อบ่งบอก สำหรับกราฟG ที่กำหนด ฟังก์ชันนี้เป็นพหุนามในt จริงๆ สำหรับกราฟตัวอย่างP ( G , t ) = t ( t − 1) ^² ( t − 2)และP ( G , 4) = 72

พหุนามสีประกอบด้วยข้อมูลเกี่ยวกับความสามารถในการระบายสีของGมากกว่าจำนวนสี ที่จริงแล้วχคือจำนวนเต็มบวกที่เล็กที่สุดที่ไม่ใช่ศูนย์ของพหุนามสีχ( G ) = min{ k  : P ( G , k ) > 0 }

การระบายสีขอบของกราฟคือการระบายสีขอบอย่างเหมาะสมซึ่งหมายถึงการกำหนดสีให้กับขอบโดยที่ไม่มีจุดยอดใดเชื่อมต่อกับขอบสองขอบที่มีสีเดียวกัน การระบายสีขอบด้วยkสีเรียกว่า การระบายสีขอบ kสี และเทียบเท่ากับปัญหาการแบ่งเซตของขอบออกเป็นk การจับคู่จำนวนสีที่น้อยที่สุดที่จำเป็นสำหรับการระบายสีขอบของกราฟGคือดัชนีสีหรือจำนวนสีของขอบχ ′ ( G ) การระบายสี แบบTaitคือการระบายสีขอบ 3 สีของกราฟลูกบาศก์ทฤษฎีบทสี่สีเทียบเท่ากับข้อ assertion ที่ว่า กราฟ ลูกบาศก์ระนาบที่ไม่มีสะพาน ทุกกราฟ ยอมรับการระบายสีแบบ Tait

การระบายสีแบบสมบูรณ์ (Total coloring)เป็นวิธีการระบายสีบนจุดยอดและขอบของกราฟ เมื่อใช้โดยไม่มีเงื่อนไขใดๆ การระบายสีแบบสมบูรณ์จะถือว่าเป็นการระบายสีที่เหมาะสมเสมอ ในแง่ที่ว่าไม่มีจุดยอดที่อยู่ติดกัน ไม่มีขอบที่อยู่ติดกัน และไม่มีขอบและจุดยอดปลายใดที่ได้รับสีเดียวกัน จำนวนสีรวมχ ″( G )ของกราฟGคือจำนวนสีน้อยที่สุดที่จำเป็นในการระบายสีแบบสมบูรณ์ใดๆของ G

สำหรับกราฟที่มีการฝังตัวอย่างแน่นหนาบนพื้นผิวการระบายสีหน้าจะเป็นปัญหาคู่ขนานกับการระบายสีจุดยอด

สำหรับกราฟGที่มีการฝังตัวที่แข็งแกร่งบนพื้นผิวที่กำหนดทิศทางได้William T. Tutte ^{[ 7 ] [ 8 ] [ 9 ]}ค้นพบว่าถ้ากราฟสามารถระบายสีหน้าได้k หน้า G จะยอมรับการไหล kที่ไม่มีที่ใดเป็นศูนย์ความเท่าเทียมกันนี้เป็นจริงถ้าพื้นผิวเป็นทรงกลม

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

ถ้าเราตีความการระบายสีกราฟที่มีdจุดยอดเป็นเวกเตอร์ใน⁠ ⁠${\displaystyle \mathbb {Z} ^{d}}$การกระทำของออโตมอร์ฟิซึมคือการเรียงสับเปลี่ยนของสัมประสิทธิ์ในเวกเตอร์การระบายสี

การกำหนดสีที่แตกต่างกันให้กับจุดยอดที่แตกต่างกัน จะทำให้ได้สีที่ถูกต้องเสมอ ดังนั้น

${\displaystyle 1\leq \chi (G)\leq n.}$

กราฟชนิดเดียวที่สามารถระบายสีได้ด้วยสีเดียวคือกราฟที่ไม่มีขอบกราฟสมบูรณ์ ที่มี จุดยอด nจุดต้องใช้ สี ในการระบายสีที่เหมาะสมที่สุด จะต้องมีขอบอย่างน้อยหนึ่งเส้นจาก m ขอบ ของกราฟระหว่างกลุ่มสีทุกคู่ ดังนั้น ${\displaystyle K_{n}}$${\displaystyle \chi (K_{n})=n}$

${\displaystyle \chi (G)(\chi (G)-1)\leq 2m.}$

โดยทั่วไปแล้ว กลุ่มของกราฟจะถูกจำกัดด้วยχหากมีฟังก์ชันบางอย่างที่ทำให้กราฟในกลุ่มนั้นสามารถระบายสีได้ด้วยสีไม่เกิน โดยที่คือจำนวนคลิกของกลุ่มนั้น สำหรับกลุ่มของกราฟสมบูรณ์ ฟังก์ชันนี้คือ ${\displaystyle {\mathcal {F}}}$${\displaystyle c}$${\displaystyle G}$${\displaystyle {\mathcal {F}}}$${\displaystyle c(\omega (G))}$${\displaystyle \omega (G)}$${\displaystyle G}$${\displaystyle c(\omega (G))=\omega (G)}$

กราฟที่ระบายสีได้ 2 สี คือกราฟสองส่วนซึ่งรวมถึงต้นไม้และป่า ตามทฤษฎีบทสี่สี กราฟระนาบทุกกราฟสามารถระบายสีได้ 4 สี

การระบายสีแบบโลภ (Greedy coloring)แสดงให้เห็นว่ากราฟทุกกราฟสามารถระบายสีได้ด้วยสีมากกว่าดีกรี สูงสุดของจุดยอดอยู่หนึ่ง สี

${\displaystyle \chi (G)\leq \Delta (G)+1.}$

กราฟสมบูรณ์มีและและวัฏจักรคี่มีและดังนั้นสำหรับกราฟเหล่านี้ ขอบเขตนี้จึงดีที่สุดเท่าที่จะเป็นไปได้ ในกรณีอื่นๆ ขอบเขตสามารถปรับปรุงได้เล็กน้อยทฤษฎีบทของบรูคส์^{[ 10 ]}ระบุว่า ${\displaystyle \chi (G)=n}$${\displaystyle \Delta (G)=n-1}$${\displaystyle \chi (G)=3}$${\displaystyle \Delta (G)=2}$

ทฤษฎีบทของบรู๊คส์ : สำหรับกราฟเชื่อมต่อแบบง่าย Gเว้นแต่ว่า Gจะเป็นกราฟสมบูรณ์หรือวัฏจักรคี่${\displaystyle \chi (G)\leq \Delta (G)}$

มีการค้นพบค่าขอบล่างหลายค่าสำหรับจำนวนสีโครมาติกในช่วงหลายปีที่ผ่านมา:

ถ้าGประกอบด้วยคลิกที่มีขนาดkแล้ว จะต้องใช้สีอย่างน้อยkสีในการระบายสีคลิกนั้น กล่าวอีกนัยหนึ่งคือ จำนวนสีที่ใช้ในการระบายสี (chromatic number) จะต้องมีค่าอย่างน้อยเท่ากับจำนวนคลิก:

${\displaystyle \chi (G)\geq \omega (G)}$

สำหรับกราฟที่สมบูรณ์แบบขอบเขตนี้ค่อนข้างแคบ การค้นหาคลิกเรียกว่าปัญหา คลิก

ขอบเขตของฮอฟฟ์แมน:ให้เป็นเมทริกซ์สมมาตรจริง โดยที่เมื่อใดก็ตามที่ไม่ใช่ขอบในกำหนด โดยที่คือค่าลักษณะเฉพาะที่ใหญ่ที่สุดและเล็กที่สุดของกำหนดโดยที่ ตามข้างต้น แล้ว: ${\displaystyle W}$${\displaystyle W_{i,j}=0}$${\displaystyle (i,j)}$${\displaystyle G}$${\displaystyle \chi _{W}(G)=1-{\tfrac {\lambda _{\max }(W)}{\lambda _{\min }(W)}}}$${\displaystyle \lambda _{\max }(W),\lambda _{\min }(W)}$${\displaystyle W}$${\textstyle \chi _{H}(G)=\max _{W}\chi _{W}(G)}$${\displaystyle W}$

${\displaystyle \chi _{H}(G)\leq \chi (G).}$

จำนวนสีของเวกเตอร์ :ให้เป็นเมทริกซ์กึ่งบวกกำหนด (positive semi-definite matrix) โดยที่เมื่อใดก็ตามที่ เป็นขอบในกำหนดให้ เป็นค่า k ที่น้อยที่สุดที่เมทริกซ์ดังกล่าวมีอยู่ จากนั้น ${\displaystyle W}$${\displaystyle W_{i,j}\leq -{\tfrac {1}{k-1}}}$${\displaystyle (i,j)}$${\displaystyle G}$${\displaystyle \chi _{V}(G)}$${\displaystyle W}$

${\displaystyle \chi _{V}(G)\leq \chi (G).}$

จำนวนโลวัสซ์ (Lovász number ):จำนวนโลวัสซ์ของกราฟส่วนเติมเต็มยังเป็นค่าต่ำสุดของจำนวนสีที่ใช้ได้ด้วย:

${\displaystyle \vartheta ({\bar {G}})\leq \chi (G).}$

จำนวนสีที่เป็นเศษส่วน :จำนวนสีที่เป็นเศษส่วนของกราฟเป็นค่าต่ำสุดของจำนวนสีทั้งหมดด้วยเช่นกัน:

${\displaystyle \chi _{f}(G)\leq \chi (G).}$

ขอบเขตเหล่านี้เรียงลำดับดังนี้:

${\displaystyle \chi _{H}(G)\leq \chi _{V}(G)\leq \vartheta ({\bar {G}})\leq \chi _{f}(G)\leq \chi (G).}$

กราฟที่มีคลิก ขนาดใหญ่ จะมีจำนวนสีสูง แต่ในทางกลับกันนั้นไม่เป็นเช่นนั้นกราฟ Grötzschเป็นตัวอย่างของกราฟ 4 สีที่ไม่มีรูปสามเหลี่ยม และตัวอย่างนี้สามารถขยายไปสู่กราฟMycielskians ได้

ทฤษฎีบท ( WT Tutte , 1947 , ^{[ 11 ]} Alexander Zykov  1949 , Jan Mycielski  1955 ): มีกราฟที่ไม่มีสามเหลี่ยมที่มีจำนวนสีสูงตามอำเภอใจ

เพื่อพิสูจน์สิ่งนี้ ทั้ง Mycielski และ Zykov ต่างก็สร้างตระกูลกราฟที่ไม่มีสามเหลี่ยม ซึ่งกำหนดโดยการอุปนัย แต่มีจำนวนสีมากตามอำเภอใจ^{[ 12 ]} Burling (1965)สร้างกล่องที่จัดเรียงตามแกนซึ่งกราฟจุดตัดไม่มีสามเหลี่ยมและต้องใช้สีจำนวนมากตามอำเภอใจในการระบายสีให้ถูกต้อง ตระกูลกราฟนี้จึงเรียกว่ากราฟ Burling กราฟประเภทเดียวกันนี้ถูกใช้สำหรับการสร้างตระกูลส่วนของเส้นตรงที่ไม่มีสามเหลี่ยมในระนาบ ซึ่งกำหนดโดย Pawlik et al. (2014) ^{[ 13 ]}แสดงให้เห็นว่าจำนวนสีของกราฟจุดตัดนั้นมากตามอำเภอใจเช่นกัน ดังนั้นจึงหมายความว่ากล่องที่จัดเรียงตามแกนในและส่วนของเส้นตรงในไม่ได้ถูกจำกัดด้วยχ ^{[ 13 ]}${\displaystyle \mathbb {R} ^{3}}$${\displaystyle \mathbb {R} ^{3}}$${\displaystyle \mathbb {R} ^{2}}$

จากทฤษฎีบทของบรู๊คส์ กราฟที่มีจำนวนสีสูงจะต้องมีดีกรีสูงสุดสูง แต่ความสามารถในการระบายสีนั้นไม่ใช่ปรากฏการณ์เฉพาะที่เท่านั้น กราฟที่มีเส้นรอบวง สูง จะดูเหมือนต้นไม้ในระดับท้องถิ่น เพราะวัฏจักรทั้งหมดมีความยาว แต่จำนวนสีของมันไม่จำเป็นต้องเป็น 2 เสมอไป

ทฤษฎีบท ( เออร์โดส ): มีกราฟที่มีเส้นรอบวงและจำนวนสีสูงตามอำเภอใจ^{[ 14 ]}

การระบายสีขอบของกราฟ Gคือการระบายสีจุดยอดของกราฟเส้น G และในทางกลับกัน ดังนั้น ${\displaystyle L(G)}$

${\displaystyle \chi '(G)=\chi (L(G)).}$

มีความสัมพันธ์อย่างแน่นแฟ้นระหว่างความสามารถในการระบายสีขอบและดีกรีสูงสุดของกราฟเนื่องจากขอบทั้งหมดที่เชื่อมต่อกับจุดยอดเดียวกันจำเป็นต้องมีสีของตัวเอง เราจึงได้ว่า ${\displaystyle \Delta (G)}$

${\displaystyle \chi '(G)\geq \Delta (G).}$

นอกจากนี้,

ทฤษฎีบทของ Kőnig : ถ้า Gเป็นเมทริกซ์สองส่วน${\displaystyle \chi '(G)=\Delta (G)}$

โดยทั่วไปแล้ว ความสัมพันธ์นี้แข็งแกร่งกว่าสิ่งที่ทฤษฎีบทของบรู๊คส์ให้ไว้สำหรับการระบายสีจุดยอดเสียอีก:

ทฤษฎีบทของวิซิง:กราฟที่มีดีกรีสูงสุดจะมีจำนวนสีของขอบเท่ากับหรือ${\displaystyle \Delta }$${\displaystyle \Delta }$${\displaystyle \Delta +1}$

กราฟจะมีk-สีได้ก็ต่อเมื่อมีทิศทางแบบไม่มีวงจรซึ่งเส้นทางที่ยาวที่สุดมีความยาวไม่เกินkนี่คือทฤษฎีบท Gallai–Hasse–Roy–Vitaver ( Nešetřil & Ossona de Mendez 2012 )

สำหรับกราฟระนาบ การระบายสีจุดยอดนั้นโดยพื้นฐานแล้วเป็นสิ่งที่ตรงกันข้ามกับการไหลที่ไม่มีจุดใดเป็นศูนย์

เกี่ยวกับกราฟอนันต์นั้น ความรู้ยังมีน้อยมาก ต่อไปนี้เป็นผลลัพธ์เพียงไม่กี่อย่างเกี่ยวกับการระบายสีกราฟอนันต์:

• ถ้ากราฟย่อยจำกัดทั้งหมดของกราฟอนันต์Gสามารถ ระบายสีได้ ด้วย k สีแล้วG ก็สามารถระบายสีได้ด้วย k สีเช่นกัน ภายใต้สมมติฐานของสัจพจน์ของการเลือกนี่คือทฤษฎีบทของเดอ บรูอิน-เออร์โดสของเดอ บรูอินและเออร์โดส (1951 )
• ถ้ากราฟยอมรับ การระบายสีแบบ n สีเต็ม สำหรับทุกn ≥ n ₀กราฟนั้นจะยอมรับการระบายสีแบบเต็มจำนวนอนันต์ ( Fawcett 1978 )

ดังที่กล่าวไว้ข้างต้นข้อสันนิษฐานของรีดในปี 1998 คือ ค่าที่ได้นั้นโดยพื้นฐานแล้วใกล้เคียงกับขอบเขตล่างมากกว่า${\displaystyle \omega (G)\leq \chi (G)\leq \Delta (G)+1.}$${\displaystyle \chi (G)\leq \left\lceil {\frac {\omega (G)+\Delta (G)+1}{2}}\right\rceil .}$

จำนวนสีของระนาบซึ่งจุดสองจุดจะอยู่ติดกันหากมีระยะห่างหนึ่งหน่วย ยังไม่เป็นที่ทราบแน่ชัด แม้ว่าจะเป็นหนึ่งใน 5, 6 หรือ 7 ก็ตามปัญหาเปิด อื่นๆ ที่เกี่ยวข้องกับจำนวนสีของกราฟ ได้แก่ข้อสันนิษฐานของ Hadwigerที่ระบุว่ากราฟทุกกราฟที่มีจำนวนสีkจะมีกราฟสมบูรณ์บนkจุดยอดเป็น กราฟ ย่อย ข้อสันนิษฐานของ Erdős –Faber–Lovász ที่กำหนดขอบเขตของจำนวนสีของการรวมกันของกราฟสมบูรณ์ที่มีจุดยอดร่วมกันอย่างมากที่สุดหนึ่งจุดในแต่ละคู่ และข้อสันนิษฐานของ Albertsonที่ว่าในบรรดา กราฟที่มีจำนวนสี kกราฟสมบูรณ์คือกราฟที่มีจำนวนจุดตัด น้อย ที่สุด

เมื่อเบิร์คฮอฟฟ์และลูอิสได้นำเสนอพหุนามสีในการโจมตีทฤษฎีบทสี่สีพวกเขาตั้งข้อสันนิษฐานว่าสำหรับกราฟระนาบพหุนามนี้ไม่มีรากในบริเวณแม้ว่าจะเป็นที่ทราบกันดีอยู่แล้วว่าพหุนามสีดังกล่าวไม่มีรากในบริเวณและ แต่ข้อสันนิษฐานของพวกเขายังคงไม่ได้รับการแก้ไข นอกจากนี้ การจำแนกลักษณะของกราฟที่มีพหุนามสีเดียวกัน และการพิจารณาว่าพหุนามใดเป็นพหุนามสี ก็ยังคงเป็นปัญหาที่ยังไม่ได้รับการแก้ไขเช่นกัน ${\displaystyle G}$${\displaystyle P(G,t)}$${\displaystyle [4,\infty )}$${\displaystyle [5,\infty )}$${\displaystyle P(G,4)\neq 0}$

การระบายสีกราฟ
การตัดสินใจ
ชื่อ	การระบายสีกราฟ, การระบายสีจุดยอด, การระบายสีk
ป้อนข้อมูล	กราฟGมีn จุดยอด โดยที่ kเป็นจำนวนเต็ม
เอาต์พุต	Gยอมรับการระบายสีจุดยอดที่เหมาะสมด้วยสีk สี หรือ ไม่?
ระยะเวลาการวิ่ง	O (2 n n ) [ 15 ]
ความซับซ้อน	NP-complete
การลดลงจาก	3. ความพึงพอใจ
แกรี่-จอห์นสัน	จีที4
การเพิ่มประสิทธิภาพ
ชื่อ	หมายเลขสี
ป้อนข้อมูล	กราฟGมี จุดยอด nจุด
เอาต์พุต	χ ( G )
ความซับซ้อน	NP-hard
ความสามารถในการประมาณค่า	O ( n (log  n ) −3 (log log  n ) 2 )
ความไม่สามารถประมาณค่าได้	O ( n 1− ε ) เว้นแต่P = NP
ปัญหาการนับ
ชื่อ	พหุนามสี
ป้อนข้อมูล	กราฟGมีn จุดยอด โดยที่ kเป็นจำนวนเต็ม
เอาต์พุต	จำนวนP  ( G , k ) ของ การระบายสี k ที่เหมาะสม ของG
ระยะเวลาการวิ่ง	O (2 n n )
ความซับซ้อน	♯P-สมบูรณ์
ความสามารถในการประมาณค่า	FPRASสำหรับกรณีที่จำกัด
ความไม่สามารถประมาณค่าได้	ไม่มีPTASเว้นแต่ P = NP

การพิจารณาว่ากราฟสามารถระบายสีด้วย 2 สีได้หรือไม่นั้น เทียบเท่ากับการพิจารณาว่ากราฟนั้นเป็นกราฟสองส่วน หรือไม่ และสามารถคำนวณได้ในเวลาเชิงเส้นโดยใช้การค้นหาแบบกว้างหรือการค้นหาแบบลึกโดยทั่วไปแล้ว จำนวนสีและสีที่สอดคล้องกันของกราฟสมบูรณ์สามารถคำนวณได้ในเวลาพหุนามโดยใช้การเขียนโปรแกรมเชิงกึ่งกำหนดสูตรปิดสำหรับพหุนามสีเป็นที่รู้จักสำหรับกราฟหลายประเภท เช่น ป่า กราฟคอร์ดัล วงจร ล้อ และบันได ดังนั้นจึงสามารถประเมินค่าเหล่านี้ได้ในเวลาพหุนาม

หากกราฟเป็นกราฟระนาบและมีความกว้างของกิ่งต่ำ (หรือเป็นกราฟที่ไม่ใช่ระนาบแต่ทราบการแบ่งกิ่ง ) ก็สามารถแก้ได้ในเวลาพหุนามโดยใช้การเขียนโปรแกรมเชิงพลวัต โดยทั่วไปแล้ว เวลาที่ใช้จะเป็นพหุนามตามขนาดของกราฟ แต่จะเป็นเลขชี้กำลังตามความกว้างของกิ่ง

การค้นหา การ ระบายสี k สีแบบใช้กำลังทั้งหมด (Brute-force)จะพิจารณาการกำหนด สี kสีให้กับ จุดยอด nจุดแต่ละแบบ และตรวจสอบว่าแต่ละแบบถูกต้องตามกฎหรือไม่ ในการคำนวณจำนวนโครมาติกและพหุนามโครมาติก จะใช้วิธีการนี้กับทุกกราฟที่มีจำนวนสี k มาก ซึ่งไม่สามารถทำได้จริง ยกเว้นกราฟที่มีขนาดเล็กที่สุดเท่านั้น ${\displaystyle k^{n}}$${\displaystyle k=1,\ldots ,n-1}$

การใช้การเขียนโปรแกรมแบบไดนามิกและขอบเขตของจำนวนเซตอิสระสูงสุด ทำให้สามารถตัดสินการระบายสี kได้ในเวลาและพื้นที่[ ^{16 ] การ}ใช้หลักการรวม-การแยกออกและอัลกอริทึมของYates สำหรับการแปลงซีตาแบบเร็ว ทำให้สามารถตัดสินการระบายสีk ได้ในเวลา ^{[ 15 ] [ 17 ] [ 18 ] [ 19 ]}สำหรับk ใดๆ อัลก อริทึมที่เร็วกว่าเป็นที่รู้จักสำหรับการระบายสี 3 และ 4 ซึ่งสามารถตัดสินได้ในเวลา^{[ 20 ]}และ[ ^{21 ] ตามลำดับ อัลกอริทึมที่เร็วกว่าแบบเลขชี้กำลังยังเป็นที่รู้จักสำหรับการระบายสี 5 และ 6 เช่นเดียวกับสำหรับ ตระกูล}กราฟที่จำกัด รวมถึงกราฟแบบเบาบาง^{[ 22 ]}${\displaystyle O(2.4423^{n})}$${\displaystyle O(2^{n}n)}$${\displaystyle O(1.3289^{n})}$${\displaystyle O(1.7272^{n})}$

การหดตัว ของกราฟGคือกราฟที่ได้จากการรวมจุดยอดuและv เข้า ด้วยกัน และลบขอบที่เชื่อมระหว่างจุดยอดทั้งสองออก ขอบที่เหลืออยู่ซึ่งเดิมเชื่อมกับuหรือvจะเชื่อมกับจุดยอดที่รวมกันใหม่ ( กล่าวคือจุดยอดที่รวมกันใหม่uv ) การดำเนินการนี้มีบทบาทสำคัญในการวิเคราะห์การระบายสีกราฟ ${\displaystyle G/uv}$

จำนวนสีตามสูตรสอดคล้องกับความสัมพันธ์เวียนเกิดดังนี้:

${\displaystyle \chi (G)={\text{min}}\{\chi (G+uv),\chi (G/uv)\}}$

ตามแนวคิดของZykov (1949)โดยที่uและvเป็นจุดยอดที่ไม่ติดกัน และคือกราฟที่มีขอบuv เพิ่มเข้ามา อัลกอริทึมหลายตัวใช้การประเมินความสัมพันธ์เวียนเกิดนี้ และต้นไม้การคำนวณที่ได้นั้นบางครั้งเรียก ว่า ต้นไม้ Zykov เวลาในการทำงานขึ้นอยู่กับฮิวริสติกในการเลือกจุดยอดuและv${\displaystyle G+uv}$

พหุนามสีสอดคล้องกับความสัมพันธ์เวียนเกิดต่อไปนี้

${\displaystyle P(G-uv,k)=P(G/uv,k)+P(G,k),}$

โดยที่uและvเป็นจุดยอดที่อยู่ติดกัน และคือกราฟที่ตัดขอบuvออกไปแทนจำนวนการระบายสีที่เหมาะสมที่เป็นไปได้ของกราฟ โดยที่จุดยอดอาจมีสีเดียวกันหรือต่างกันก็ได้ การระบายสีที่เหมาะสมเหล่านี้เกิดขึ้นจากกราฟสองแบบที่แตกต่างกัน อธิบายได้ว่า ถ้าจุดยอดuและvมีสีต่างกัน เราอาจพิจารณากราฟที่uและvเป็นจุดยอดที่อยู่ติดกันก็ได้ ถ้าuและvมีสีเดียวกัน เราอาจพิจารณากราฟที่uและvเป็นจุดยอดที่ยุบรวมกันก็ได้ ความสงสัยของ Tutte เกี่ยวกับคุณสมบัติของกราฟอื่นๆ ที่สอดคล้องกับความสัมพันธ์เวียนเกิดนี้ ทำให้เขาค้นพบการวางนัยทั่วไปแบบทวิภาคของพหุนามสี ซึ่งก็คือ พหุ นาม Tutte${\displaystyle G-uv}$${\displaystyle P(G-uv,k)}$

นิพจน์เหล่านี้ก่อให้เกิดขั้นตอนแบบเรียกซ้ำที่เรียกว่าอัลกอริทึมการลบ-การหดตัวซึ่งเป็นพื้นฐานของอัลกอริทึมหลายอย่างสำหรับการระบายสีกราฟ เวลาในการทำงานเป็นไปตามความสัมพันธ์แบบเรียกซ้ำเดียวกันกับจำนวนฟิโบนาชชีดังนั้นในกรณีที่เลวร้ายที่สุด อัลกอริทึมจะทำงานในเวลาภายในปัจจัยพหุนามสำหรับ จุดยอด nจุดและขอบm เส้น ^{[ 23 ]}การวิเคราะห์สามารถปรับปรุงได้ภายในปัจจัยพหุนามของจำนวนต้นไม้แผ่ขยายของกราฟอินพุต^{[ 24 ]}ในทางปฏิบัติกลยุทธ์การแบ่งแยกและขอบเขต และการปฏิเสธ ความเหมือนกันของกราฟจะถูกนำมาใช้เพื่อหลีกเลี่ยงการเรียกซ้ำบางอย่าง เวลาในการทำงานขึ้นอยู่กับฮิวริสติกที่ใช้ในการเลือกคู่จุดยอด ${\displaystyle \left({\tfrac {1+{\sqrt {5}}}{2}}\right)^{n+m}=O(1.6180^{n+m})}$${\displaystyle t(G)}$

อัลกอริทึมแบบโลภ (greedy algorithm)พิจารณาจุดยอดตามลำดับที่กำหนด, ..., และกำหนดสีที่เล็กที่สุดที่ว่างอยู่ซึ่งไม่ได้ถูกใช้โดยจุดยอดข้างเคียงของ ให้กับจุดยอด ในกลุ่ม, ..., โดยเพิ่มสีใหม่หากจำเป็น คุณภาพของการระบายสีที่ได้ขึ้นอยู่กับลำดับที่เลือก มีลำดับหนึ่งที่นำไปสู่การระบายสีแบบโลภด้วยจำนวนสีที่เหมาะสมที่สุด ในทางกลับกัน การระบายสีแบบโลภอาจไม่ดีเท่าที่ควร ตัวอย่างเช่นกราฟมงกุฎที่มี จุดยอด nจุด อาจระบายสีได้ 2 สี แต่มีลำดับที่นำไปสู่การระบายสีแบบโลภด้วยสี ${\displaystyle v_{1}}$${\displaystyle v_{n}}$${\displaystyle v_{i}}$${\displaystyle v_{i}}$${\displaystyle v_{1}}$${\displaystyle v_{i-1}}$${\displaystyle \chi (G)}$${\displaystyle n/2}$

สำหรับกราฟคอร์ดัลและกรณีพิเศษของกราฟคอร์ดัล เช่นกราฟช่วงและกราฟความไม่แตกต่างอัลกอริทึมการระบายสีแบบโลภ (greedy coloring algorithm) สามารถใช้หาการระบายสีที่เหมาะสมที่สุดได้ในเวลาพหุนาม โดยเลือกการเรียงลำดับจุดยอดให้เป็นลำดับย้อนกลับของการเรียงลำดับการกำจัดที่สมบูรณ์แบบสำหรับกราฟนั้น กราฟที่เรียงลำดับได้อย่างสมบูรณ์แบบ (perfectly orderable graphs)ขยายคุณสมบัตินี้ แต่การหาการเรียงลำดับที่สมบูรณ์แบบสำหรับกราฟเหล่านี้เป็นปัญหา NP-hard

หากจุดยอดถูกจัดเรียงตามดีกรีการระบายสีแบบโลภที่ได้จะใช้สีไม่เกินหนึ่งสี มากกว่าดีกรีสูงสุดของกราฟ วิธีการนี้บางครั้งเรียกว่าอัลกอริทึม Welsh–Powell ^{[ 25 ]}วิธีการอีกวิธีหนึ่งที่พัฒนาโดยBrélazจะกำหนดลำดับแบบไดนามิกในขณะที่อัลกอริทึมดำเนินการ โดยเลือกจุดยอดที่อยู่ติดกับจำนวนสีที่แตกต่างกันมากที่สุดถัดไป^{[ 26 ]} วิธี การระบายสีกราฟแบบโลภอื่นๆ อีกมากมายก็ใช้หลักการระบายสีแบบโลภในลักษณะเดียวกันสำหรับกลยุทธ์แบบคงที่หรือแบบไดนามิกเฉพาะในการจัดเรียงจุดยอด อัลกอริทึมเหล่านี้บางครั้งเรียกว่าอัลกอริทึม การระบายสีแบบลำดับ${\displaystyle {\text{max}}_{i}{\text{ min}}\{d(x_{i})+1,i\}}$

จำนวนสีสูงสุด (หรือแย่ที่สุด) ที่สามารถได้มาโดยอัลกอริทึมแบบโลภ (greedy algorithm) โดยใช้ลำดับจุดยอดที่เลือกมาเพื่อให้จำนวนนี้มีค่าสูงสุด เรียกว่าเลขกรุนดี (Grundy number ) ของกราฟ

สองวิธีฮิวริสติกส์ที่รู้จักกันดีซึ่งใช้เวลาในการคำนวณแบบพหุนามสำหรับการระบายสีกราฟ ได้แก่ อัลกอริทึม DSaturและ อัลก อริทึม Recursive Largest First (RLF)

เช่นเดียวกับอัลกอริธึมการระบายสีแบบโลภ (greedy colouring algorithm ) DSatur จะระบายสีจุดยอดของกราฟทีละจุด โดยใช้สีที่ยังไม่ได้ใช้ก่อนหน้านี้เมื่อจำเป็น เมื่อจุดยอด ใหม่ ได้รับการระบายสีแล้ว อัลกอริธึมจะพิจารณาว่าจุดยอดใดในบริเวณใกล้เคียงที่ยังไม่ได้รับการระบายสีนั้นมีจำนวนสีที่แตกต่างกันมากที่สุด และจะระบายสีจุดยอดนั้นต่อไป ซึ่งค่านี้เรียกว่าระดับความอิ่มตัว (degree of saturation ) ของจุดยอดนั้น

อัลกอริทึมค้นหาค่าที่ใหญ่ที่สุดแบบเรียกซ้ำทำงานในลักษณะที่แตกต่างออกไป โดยสร้างกลุ่มสีแต่ละกลุ่มทีละกลุ่ม โดยจะทำเช่นนั้นด้วยการระบุกลุ่มจุดยอดอิสระที่ใหญ่ที่สุดในกราฟโดยใช้กฎฮิวริสติกเฉพาะ จากนั้นจะกำหนดสีเดียวกันให้กับจุดยอดเหล่านั้นและลบออกจากกราฟ การกระทำเหล่านี้จะถูกทำซ้ำกับกราฟย่อยที่เหลืออยู่จนกว่าจะไม่มีจุดยอดเหลืออยู่

ความซับซ้อนในกรณีที่เลวร้ายที่สุดของ DSatur คือโดยที่คือจำนวนจุดยอดในกราฟ อัลกอริทึมยังสามารถนำไปใช้โดยใช้ฮีปไบนารีเพื่อจัดเก็บระดับความอิ่มตัว โดยทำงานในโดยที่คือจำนวนขอบในกราฟ^{[ 27 ] ซึ่งทำให้การทำงานเร็วขึ้นมากกับ กราฟ}แบบเบาบาง ความซับซ้อนโดยรวมของ RLF สูงกว่าDSatur เล็กน้อย ที่[ ^{27 ]}${\displaystyle O(n^{2})}$${\displaystyle n}$${\displaystyle O((n+m)\log n)}$${\displaystyle m}$${\displaystyle O(mn)}$

DSatur และ RLF มีค่าที่แน่นอนสำหรับกราฟแบบสองส่วนวงจรและวงล้อ^{[ 27 ]}

เป็นที่ทราบกันว่า กราฟสี χสามารถ ระบายสี ด้วยสี c ได้ในแบบจำลอง LOCAL แบบกำหนดได้ ในจำนวนรอบ โดย ที่ เป็นที่ทราบกันดีอยู่แล้วว่า ขอบเขตล่างของจำนวนรอบที่สอดคล้องกันนั้นมีค่าเท่ากัน ขอบเขตล่างนี้ยังคงใช้ได้แม้ว่าจะอนุญาตให้ใช้คอมพิวเตอร์ควอนตัมที่สามารถแลกเปลี่ยนข้อมูลควอนตัมได้ โดยอาจมีสถานะพันกันที่แบ่งปันไว้ล่วงหน้า ${\displaystyle O(n^{1/\alpha })}$${\displaystyle \alpha =\left\lfloor {\frac {c-1}{\chi -1}}\right\rfloor }$${\displaystyle \Omega (n^{1/\alpha })}$

ในสาขาของอัลกอริทึมแบบกระจายการระบายสีกราฟมีความเกี่ยวข้องอย่างใกล้ชิดกับปัญหาการทำลายสมมาตร อัลกอริทึมแบบสุ่มที่ทันสมัยในปัจจุบันนั้นเร็วกว่าอัลกอริทึมแบบกำหนดสำหรับระดับสูงสุด Δ ที่มีขนาดใหญ่พอสมควร อัลกอริทึมแบบสุ่มที่เร็วที่สุดใช้เทคนิคการทดลองหลายครั้งโดย Schneider และ Wattenhofer ^{[ 28 ]}

ในกราฟสมมาตรอั ลกอริทึมแบบกระจาย เชิงกำหนดไม่สามารถหาการระบายสีจุดยอดที่เหมาะสมได้ จำเป็นต้องมีข้อมูลเสริมบางอย่างเพื่อทำลายสมมาตร สมมติฐานมาตรฐานคือ ในตอนเริ่มต้น โหนดแต่ละโหนดมีตัวระบุที่ไม่ซ้ำกันเช่น จากเซต {1, 2, ..., n } กล่าวอีกนัยหนึ่ง เราสมมติว่าเราได้รับ สี nสี ความท้าทายคือการลดจำนวนสีจากnเป็น เช่น Δ + 1 ยิ่งใช้สีมากขึ้น เช่นO (Δ) แทนที่จะเป็น Δ + 1 จำนวนรอบการสื่อสารที่ต้องการก็จะยิ่งน้อยลง^{[ 28 ]}

เวอร์ชันแบบกระจายที่ตรงไปตรงมาของอัลกอริทึมแบบโลภ (greedy algorithm) สำหรับการระบายสี (Δ + 1) ต้องใช้รอบการสื่อสาร Θ( n ) ในกรณีที่เลวร้ายที่สุด – อาจจำเป็นต้องส่งต่อข้อมูลจากด้านหนึ่งของเครือข่ายไปยังอีกด้านหนึ่ง

กรณีที่น่าสนใจที่สุดที่ง่ายที่สุดคือวงจร n Richard Cole และUzi Vishkin ^{[ 29 ]}แสดงให้เห็นว่ามีอัลกอริทึมแบบกระจายที่ลดจำนวนสีจากnเป็นO (log  n ) ในขั้นตอนการสื่อสารแบบซิงโครนัสหนึ่งขั้นตอน โดยการทำซ้ำขั้นตอนเดียวกันนี้ จะสามารถระบายสี วงจร n ด้วย 3 สีได้ ใน ขั้นตอนการสื่อสาร O ( log * n ) (โดยสมมติว่าเรามีตัวระบุโหนดที่ไม่ซ้ำกัน)  

ฟังก์ชันlog *ซึ่งเป็นลอการิทึมแบบวนซ้ำเป็นฟังก์ชันที่เติบโตช้ามาก "เกือบจะคงที่" ดังนั้นผลลัพธ์ของ Cole และ Vishkin จึงทำให้เกิดคำถามว่ามี อัลกอริทึมแบบกระจายที่ มีเวลาคงที่สำหรับการระบายสี 3 สีในn - cycle หรือ ไม่ Linial (1992)แสดงให้เห็นว่าสิ่งนี้เป็นไปไม่ได้: อัลกอริทึมแบบกระจายเชิงกำหนดใด ๆ ต้องใช้ขั้นตอนการสื่อสาร Ω( log *  n ) เพื่อลด การระบายสี nสีให้เหลือการระบายสี 3 สีในn -cycle

เทคนิคของ Cole และ Vishkin สามารถนำไปใช้กับกราฟที่มีดีกรีจำกัดใดๆ ก็ได้เช่นกัน เวลาในการทำงานคือ poly(Δ) + O ( log *  n ) ^{[ 30 ]}เทคนิคนี้ได้รับการขยายไปยังกราฟดิสก์หน่วยโดย Schneider และ Wattenhofer ^{[ 31 ]}อัลกอริทึมแบบกำหนดที่เร็วที่สุดสำหรับการระบายสี (Δ + 1) สำหรับ Δ ขนาดเล็กนั้นมาจาก Leonid Barenboim, Michael Elkin และ Fabian Kuhn ^{[ 32 ]}อัลกอริทึมของ Barenboim et al. ทำงานในเวลาO (Δ) +  log * ( n )/2 ซึ่งเหมาะสมที่สุดในแง่ของnเนื่องจากปัจจัยคงที่ 1/2 ไม่สามารถปรับปรุงได้เนื่องจากขอบเขตล่างของ Linial Panconesi & Srinivasan (1996)ใช้การแยกส่วนเครือข่ายเพื่อคำนวณการระบายสี Δ+1 ในเวลา ${\displaystyle 2^{O\left({\sqrt {\log n}}\right)}}$

ปัญหาการระบายสีขอบได้รับการศึกษาในแบบจำลองแบบกระจายเช่นกันPanconesi & Rizzi (2001)บรรลุการระบายสี (2Δ − 1) ใน เวลา O (Δ +  log *  n ) ในแบบจำลองนี้ ขอบล่างสำหรับการระบายสีจุดยอดแบบกระจายเนื่องจากLinial (1992)ใช้ได้กับปัญหาการระบายสีขอบแบบกระจายเช่นกัน

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

การระบายสีกราฟนั้นยากในเชิงการคำนวณการตัดสินใจว่ากราฟที่กำหนดนั้นยอมรับ การระบายสี k สีสำหรับk ที่กำหนดหรือไม่นั้นเป็น ปัญหา NP-completeยกเว้นกรณีk ∈ {0,1,2} โดยเฉพาะอย่างยิ่ง การคำนวณจำนวนโครมาติกนั้นเป็นปัญหา NP-hard ^{[ 34 ]}ปัญหาการระบายสี 3 สียังคงเป็นปัญหา NP-complete แม้แต่บนกราฟระนาบ 4 -regular ^{[ 35 ]}อย่างไรก็ตาม บนกราฟที่มีดีกรีสูงสุด 3 หรือน้อยกว่าทฤษฎีบทของ Brooksบ่งชี้ว่าปัญหาการระบายสี 3 สีสามารถแก้ไขได้ในเวลาเชิงเส้น นอกจากนี้ สำหรับทุกk > 3 การระบายสี kสีของกราฟระนาบมีอยู่จริงตามทฤษฎีบทสี่สีและเป็นไปได้ที่จะหาการระบายสีดังกล่าวในเวลาพหุนาม อย่างไรก็ตาม การหาการ ระบายสี 4 สีที่เล็กที่สุดตามลำดับ ตัวอักษรของกราฟระนาบนั้นเป็นปัญหา NP-complete ^{[ 36 ]}

อัลกอริทึมการประมาณค่าที่เป็นที่รู้จักดีที่สุดจะคำนวณการระบายสีที่มีขนาดไม่เกินปัจจัยO ( n (log log  n ) ² (log n) ⁻³ ) ของจำนวนสี^{[ 37 ]}สำหรับε  > 0 ทั้งหมด การประมาณจำนวนสีภายในn ^{1− ε}เป็นปัญหา NP- hard ^{[ 38 ]}

นอกจากนี้ การระบายสีกราฟที่ระบายสีได้ 3 สีด้วย 5 สี^{[ 39 ]}กราฟที่ระบายสีได้ 4 สีด้วย 7 สี^{[ 39 ]}และ กราฟที่ระบายสีได้ k สี ด้วยสีสำหรับk ≥ 5 ^{[ 40 ] ยังเป็น NP-hard อีกด้วย}${\displaystyle \textstyle {\binom {k}{\lfloor k/2\rfloor }}-1}$

การคำนวณสัมประสิทธิ์ของพหุนามสีนั้นยากระดับ#P-hardอันที่จริง แม้แต่การคำนวณค่าของ พหุนามสีก็ยังยากระดับ #P-hard ที่จุดตรรกยะk ใดๆ ยกเว้นk  = 1 และk  = 2 ^{[ 41 ]}ไม่มีFPRAS สำหรับการ ^{ประเมิน}พหุนามสีที่จุดตรรกยะk  ≥ 1.5 ใดๆ ยกเว้นk  = 2 เว้นแต่ว่าNP  =  RP [ ^{42 ]}${\displaystyle \chi (G,k)}$

สำหรับการระบายสีขอบ การพิสูจน์ผลลัพธ์ของ Vizing ให้ขั้นตอนวิธีที่ใช้สีอย่างมากที่สุด Δ+1 สี อย่างไรก็ตาม การตัดสินใจเลือกระหว่างค่าที่เป็นไปได้สองค่าสำหรับจำนวนสีของขอบนั้นเป็นปัญหา NP-complete ^{[ 43 ]}ในแง่ของขั้นตอนวิธีประมาณค่า ขั้นตอนวิธีของ Vizing แสดงให้เห็นว่าจำนวนสีของขอบสามารถประมาณค่าได้ภายใน 4/3 และผลลัพธ์ความยากแสดงให้เห็นว่าไม่มีขั้นตอนวิธี (4/3 −  ε ) สำหรับε > 0 ใดๆ เว้นแต่P = NPผลลัพธ์เหล่านี้เป็นหนึ่งในผลลัพธ์ที่เก่าแก่ที่สุดในวรรณกรรมของขั้นตอนวิธีประมาณค่า แม้ว่าทั้งสองเอกสารจะไม่ได้ใช้แนวคิดนั้นอย่างชัดเจนก็ตาม^{[ 44 ]}

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

รายละเอียดของปัญหาการจัดตารางเวลาจะกำหนดโครงสร้างของกราฟ ตัวอย่างเช่น เมื่อจัดสรรเครื่องบินให้กับเที่ยวบิน กราฟความขัดแย้งที่เกิดขึ้นจะเป็นกราฟช่วงดังนั้นปัญหาการระบายสีจึงสามารถแก้ไขได้อย่างมีประสิทธิภาพ ในการจัดสรรแบนด์วิดท์ให้กับสถานีวิทยุ กราฟความขัดแย้งที่เกิดขึ้นจะเป็นกราฟวงกลมหน่วยดังนั้นปัญหาการระบายสีจึงสามารถประมาณค่าได้ด้วยวิธี 3-approximable

คอมไพเลอร์คือโปรแกรมคอมพิวเตอร์ที่แปลงภาษาคอมพิวเตอร์ หนึ่ง ไปเป็นอีกภาษาหนึ่ง เพื่อปรับปรุงความเร็วในการประมวลผลของโค้ดที่ได้ หนึ่งในเทคนิคการปรับปรุงประสิทธิภาพของคอมไพเลอร์คือการจัดสรรรีจิสเตอร์โดยค่าที่ใช้บ่อยที่สุดของโปรแกรมที่คอมไพล์แล้วจะถูกเก็บไว้ในรีจิสเตอร์ของโปรเซสเซอร์ที่ ทำงานเร็ว ในอุดมคติแล้ว ค่าต่างๆ จะถูกกำหนดให้กับรีจิสเตอร์เพื่อให้ค่าเหล่านั้นสามารถอยู่ในรีจิสเตอร์ได้เมื่อมีการใช้งาน

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

ปัญหาของการระบายสีกราฟเกิดขึ้นในหลายพื้นที่ปฏิบัติ เช่น การจัดตารางการแข่งขันกีฬา^{[ 47 ]}การออกแบบแผนผังที่นั่ง^{[ 48 ]}การจัดตารางสอบ^{[ 49 ]}การจัดตารางเวลารถแท็กซี่^{[ 50 ]}และการแก้ปริศนาซูโดกุ^{[ 51 ]}

ทฤษฎีแรมซีย์ศึกษาปัญหาการระบายสีที่ไม่เหมาะสมประเภทสำคัญประเภทหนึ่งโดยที่ขอบของกราฟจะถูกกำหนดสี และไม่มีข้อจำกัดเกี่ยวกับสีของขอบที่เชื่อมต่อ ตัวอย่างง่ายๆ คือทฤษฎีบทเกี่ยวกับเพื่อนและคนแปลกหน้าซึ่งกล่าวว่าในการระบายสีขอบใดๆ ของกราฟสมบูรณ์ที่มีหกจุดยอด จะมีสามเหลี่ยมสีเดียวเสมอ มักอธิบายโดยการกล่าวว่ากลุ่มคนหกคนจะมีคนแปลกหน้าสามคนหรือคนรู้จักสามคน ทฤษฎีแรมซีย์เกี่ยวข้องกับการวางนัยทั่วไปของแนวคิดนี้เพื่อค้นหาความสม่ำเสมอท่ามกลางความไม่เป็นระเบียบ โดยค้นหาเงื่อนไขทั่วไปสำหรับการมีอยู่ของกราฟย่อยสีเดียวที่มีโครงสร้างที่กำหนด ${\displaystyle K_{6}}$

การระบายสีแบบโมดูลาร์เป็นวิธีการระบายสีกราฟชนิดหนึ่ง โดยสีของแต่ละจุดยอดจะเป็นผลรวมของสีของจุดยอดที่อยู่ติดกัน

ให้เป็นจำนวนสี โดยที่คือเซตของจำนวนเต็มมอดูลัสซึ่งประกอบด้วยสมาชิก (หรือสี) ขั้นแรก เราจะระบายสีแต่ละจุดยอดใน โดยใช้สมาชิกของโดยอนุญาตให้จุดยอดที่อยู่ติดกันสองจุดมีสีเดียวกันได้ กล่าวอีกนัยหนึ่ง เราต้องการให้ เป็นการระบายสีที่ทำให้โดยที่จุดยอดที่อยู่ติดกันสามารถมีสีเดียวกันได้ ${\displaystyle k\geq 2}$${\displaystyle \mathbb {Z} _{k}}$${\displaystyle k}$${\displaystyle 0,1,2,...,k-2,k-1}$${\displaystyle G}$${\displaystyle \mathbb {Z} _{k}}$${\displaystyle c}$${\displaystyle c:V(G)\rightarrow \mathbb {Z} _{k}}$

สำหรับแต่ละจุดยอดในผลรวมสีของ, , คือผลรวมของจุดยอดที่อยู่ติดกันทั้งหมดโดยหารด้วยผลรวมสีของจะใช้สัญลักษณ์ แทน ${\displaystyle v}$${\displaystyle G}$${\displaystyle v}$${\displaystyle \sigma (v)}$${\displaystyle v}$${\displaystyle k}$${\displaystyle v}$

${\displaystyle \sigma (v)=\sum _{u\in N(v)}c(u),}$

โดยที่เป็นจุดยอดใดๆ ในบริเวณใกล้เคียงกับ, . จากนั้นเราจะระบายสีจุดยอดแต่ละจุดด้วยสีใหม่ที่กำหนดโดยผลรวมของจุดยอดที่อยู่ติดกัน กราฟมีการระบายสีแบบมอดูลาร์ ถ้าสำหรับทุกคู่ของจุดยอดที่อยู่ติดกันและ, . จำนวนสีมอดูลาร์ของ, , คือค่าต่ำสุดของ ที่ทำให้มีการระบายสีแบบมอดูลา ร์ ของอยู่${\displaystyle u}$${\displaystyle v}$${\displaystyle N(v)}$${\displaystyle G}$${\displaystyle k}$${\displaystyle a}$${\displaystyle b}$${\displaystyle \sigma (a)\neq \sigma (b)}$${\displaystyle G}$${\displaystyle mc(G)}$${\displaystyle k}$${\displaystyle k}$${\displaystyle G}$

ตัวอย่างเช่น สมมติว่ามีจุดยอดหนึ่งที่อยู่ติดกับจุดยอดอีกสองจุดที่มีสีที่กำหนดไว้คือ , และ(นั่นคือ) ผลรวมของสีจะเป็นซึ่งจะเป็นสีใหม่ของจุดยอดเราจะทำซ้ำกระบวนการนี้สำหรับทุกจุดยอดในถ้าจุดยอดที่อยู่ติดกันไม่มีจุดใดมีผลรวมของสีเท่ากัน จะมี การระบายสี แบบโมดูลัส${\displaystyle v}$${\displaystyle 0,1,1}$${\displaystyle 3{\bmod {4}}}$${\displaystyle k=4}$${\displaystyle \sigma (v)=(0+1+1+3){\bmod {4}}=5{\bmod {4}}=1{\bmod {4}}}$${\displaystyle v}$${\displaystyle G}$${\displaystyle G}$${\displaystyle 4}$

การระบายสีสามารถนำมาพิจารณาใช้กับกราฟที่มีเครื่องหมายและกราฟ กำไร ได้เช่นกัน

• กราฟวิกฤต
• เกมระบายสีกราฟ
• กราฟโฮโมมอร์ฟิซึม
• การก่อสร้างฮาโยส
• คณิตศาสตร์ของซูโดกุ
• กราฟหลายส่วน
• กราฟที่สามารถระบายสีได้อย่างเป็นเอกลักษณ์

วิกิมีเดียคอมมอนส์มีสื่อที่เกี่ยวข้องกับ การ ระบายสีกราฟ

• GColคือไลบรารี Python แบบโอเพนซอร์สสำหรับระบายสีกราฟ
• ชุด อัลกอริธึมระบายสีกราฟประสิทธิภาพสูงประกอบด้วยอัลกอริธึม 8 แบบที่แตกต่างกัน (เขียนด้วยภาษา C++) ซึ่งใช้ในหนังสือ " A Guide to Graph Colouring: Algorithms and Applications" (Springer International Publishers, 2015)
• CoLoRaTiOnโดย Jim Andrews และ Mike Fellows เป็นเกมระบายสีกราฟ
• ลิงก์ไปยังซอร์สโค้ดของโปรแกรมระบายสีกราฟ (Graph Coloring) ที่เก็บถาวรเมื่อวันที่ 4 กรกฎาคม 2551 ที่Wayback Machine
• โค้ดสำหรับคำนวณพหุนาม Tutte, Chromatic และ Flow อย่างมีประสิทธิภาพเก็บถาวรเมื่อวันที่ 16 เมษายน 2551 ที่Wayback Machineโดย Gary Haggard, David J. Pearce และ Gordon Royle
• แอปพลิเคชันบนเว็บสำหรับระบายสีกราฟโดย โฮเซ่ อันโตนิโอ มาร์ติน เอช.