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

โดยทั่วไปแล้ว การเลือกเรียงลำดับจุดยอดที่แตกต่างกันจะทำให้ได้สีที่แตกต่างกันสำหรับกราฟที่กำหนด ดังนั้นการศึกษาเกี่ยวกับการระบายสีแบบโลภ (greedy coloring) ส่วนใหญ่จึงเกี่ยวข้องกับการหาลำดับที่ดี มักจะมีลำดับที่ให้สีที่ดีที่สุดเสมอ แต่ถึงแม้ว่าจะสามารถหาลำดับดังกล่าวได้สำหรับกราฟบางประเภท แต่การหาลำดับที่ดีที่สุดโดยทั่วไปนั้นทำได้ยาก กลยุทธ์ที่ใช้กันทั่วไปสำหรับการเรียงลำดับจุดยอด ได้แก่ การวางจุดยอดที่มีดีกรีสูงกว่าไว้ก่อนจุดยอดที่มีดีกรีต่ำกว่า หรือการเลือกจุดยอดที่มีสีให้เลือกน้อยกว่าแทนจุดยอดที่มีข้อจำกัดน้อยกว่า

การระบายสีแบบโลภ (Greedy coloring) เป็นวิธีการระบายสีแบบออนไลน์โดยไม่จำเป็นต้องรู้โครงสร้างของส่วนที่ยังไม่ได้ระบายสีของกราฟ หรืออาจเลือกสีอื่นที่ไม่ใช่สีแรกที่หาได้ เพื่อลดจำนวนสีทั้งหมด อัลกอริทึมการระบายสีแบบโลภถูกนำไปประยุกต์ใช้ในปัญหาการจัดตารางเวลาและ การจัดสรรรี จิสเตอร์การวิเคราะห์เกมเชิงผสม และการพิสูจน์ผลลัพธ์ทางคณิตศาสตร์อื่นๆ รวมถึงทฤษฎีบทของบรูคส์เกี่ยวกับความสัมพันธ์ระหว่างการระบายสีและดีกรี แนวคิดอื่นๆ ในทฤษฎีกราฟที่ได้มาจากวิธีการระบายสีแบบโลภ ได้แก่จำนวนกรุนดี (Grundy number ) ของกราฟ (จำนวนสีที่มากที่สุดที่สามารถหาได้จากการระบายสีแบบโลภ) และกราฟที่ระบายสีได้ดี (well-colored graphs ) ซึ่งเป็นกราฟที่การระบายสีแบบโลภทั้งหมดใช้จำนวนสีเท่ากัน

การระบายสีแบบโลภสำหรับลำดับจุดยอดที่กำหนดสามารถคำนวณได้ด้วยอัลกอริทึมที่ทำงานในเวลาเชิงเส้นอัลกอริทึมจะประมวลผลจุดยอดตามลำดับที่กำหนด โดยกำหนดสีให้กับแต่ละจุดยอดเมื่อประมวลผลเสร็จ สีอาจแสดงด้วยตัวเลขและแต่ละจุดยอดจะได้รับสีที่มีตัวเลขน้อยที่สุดที่ยังไม่ได้ถูกใช้โดยจุดยอดข้างเคียง เพื่อหาสีที่เล็กที่สุดที่มีอยู่ อาจใช้อาร์เรย์เพื่อนับจำนวนจุดยอดข้างเคียงของแต่ละสี (หรืออีกทางหนึ่ง เพื่อแสดงเซตของสีของจุดยอดข้างเคียง) จากนั้นสแกนอาร์เรย์เพื่อหาดัชนีของศูนย์ตัวแรก^{[ 2 ]}${\displaystyle 0,1,2,\dots }$

ในภาษา Pythonสามารถแสดงอัลกอริทึมได้ดังนี้:

def first_available ( colors ): """คืนค่าจำนวนเต็มที่ไม่เป็นลบที่เล็กที่สุดที่ไม่อยู่ในชุดสีที่กำหนด "" color = 0 while color in colors : color += 1 return colordef greedy_coloring ( G , order ): """ค้นหาการระบายสีแบบโลภของ G ตามลำดับที่กำหนด" สมมติว่าการแสดงผลของ G เป็นแบบเดียวกับ https://www.python.org/doc/essays/graphs/  ที่อนุญาตให้วนซ้ำเพื่อนบ้านของโหนด/จุดยอด โดยใช้ "for w in G[node]"  ค่าที่ส่งคืนเป็นพจนานุกรมที่แมปจุดยอดกับสี """ coloring = dict () for node in order : used_neighbour_colors = { coloring [ nbr ] for nbr in G [ node ] if nbr in coloring } coloring [ node ] = first_available ( used_neighbour_colors ) return coloring

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

อัลกอริทึมทางเลือกที่ให้การระบายสีแบบเดียวกัน^{[ 3 ]}คือการเลือกเซตของจุดยอดที่มีแต่ละสีทีละสี ในวิธีนี้ แต่ละคลาสสีจะถูกเลือกโดยการสแกนผ่านจุดยอดตามลำดับที่กำหนด เมื่อการสแกนนี้พบจุดยอดที่ยังไม่ได้ระบายสีซึ่งไม่มีเพื่อนบ้านในมันจะเพิ่มเข้าไปใน ด้วยวิธีนี้จะกลายเป็นเซตอิสระสูงสุดในบรรดาจุดยอดที่ยังไม่ได้รับการกำหนดสีที่เล็กกว่า อัลกอริทึมจะค้นหาคลาสสีซ้ำๆ ด้วยวิธีนี้จนกว่าจุดยอดทั้งหมดจะถูกระบายสี อย่างไรก็ตาม วิธีนี้เกี่ยวข้องกับการสแกนกราฟหลายครั้ง ครั้งละหนึ่งคลาสสี แทนที่จะใช้วิธีที่ระบุไว้ข้างต้นซึ่งใช้การสแกนเพียงครั้งเดียว^{[ 4 ]}${\displaystyle C}$${\displaystyle v}$${\displaystyle C}$${\displaystyle v}$${\displaystyle C}$${\displaystyle C}$

ลำดับที่แตกต่างกันของจุดยอดในกราฟอาจทำให้การระบายสีแบบโลภ (greedy coloring) ใช้จำนวนสีที่แตกต่างกัน ตั้งแต่จำนวนสีที่เหมาะสมที่สุด ไปจนถึงในบางกรณี จำนวนสีที่เป็นสัดส่วนกับจำนวนจุดยอดในกราฟ ตัวอย่างเช่นกราฟมงกุฎ (กราฟที่เกิดจาก เซต ของจุดยอดn /2 สอง เซตที่ไม่ซ้ำกัน{ a1 _, a2 _, ... } และ{ b1 , b2 _, ... } โดยการเชื่อมต่อ_ai กับ bj เมื่อใดก็ตามที่i ≠ j )อาจ_{เป็นกรณี}ที่ยากเป็นพิเศษสำหรับการระบายสีแบบโลภ ด้วยลำดับจุดยอด a1, b1 , _a2 , b2 , _...การ_{ระบายสี}แบบ_{โลภจะ}ใช้ n / 2 สี คือหนึ่งสีสำหรับแต่ละคู่( ai , bi )อย่างไรก็ตาม จำนวนสีที่เหมาะสมที่สุดสำหรับกราฟนี้คือสองสี คือสีหนึ่งสำหรับจุดยอด_{ai และ}อีก_สีหนึ่งสำหรับจุดยอดbi ^{[ 5 ]}นอกจากนี้ยังมีกราฟที่การเรียงลำดับจุดยอดแบบสุ่มมีโอกาสสูงที่จะนำไปสู่จำนวนสีที่มากกว่าค่าต่ำสุดมาก^{[ 6 ]}ดังนั้น การเลือกการเรียงลำดับจุดยอดอย่างระมัดระวังจึงมีความสำคัญในการระบายสีแบบโลภ

จุดยอดของกราฟใดๆ อาจถูกจัดเรียงในลักษณะที่อัลกอริทึมแบบโลภสร้างการระบายสีที่เหมาะสมที่สุดได้เสมอ เพราะเมื่อกำหนดการระบายสีที่เหมาะสมที่สุดแล้ว เราสามารถจัดเรียงจุดยอดตามสีได้ จากนั้นเมื่อเราใช้อัลกอริทึมแบบโลภกับการจัดเรียงนี้ การระบายสีที่ได้จะเป็นการระบายสีที่เหมาะสมที่สุดโดยอัตโนมัติ^{[ 7 ]}อย่างไรก็ตาม เนื่องจากปัญหาการระบายสีกราฟที่เหมาะสมที่สุดเป็น ปัญหา NP-completeปัญหาย่อยใดๆ ที่จะช่วยให้สามารถแก้ปัญหานี้ได้อย่างรวดเร็ว รวมถึงการหาลำดับที่เหมาะสมที่สุดสำหรับการระบายสีแบบโลภ จึงเป็นปัญหาNP- hard ^{[ 8 ]}

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

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

จำนวนสีที่ได้จากการระบายสีแบบโลภสำหรับลำดับที่แย่ที่สุดของกราฟที่กำหนดเรียกว่าจำนวนกรุนดี [ ^{12 ] เช่น} เดียวกับการหาลำดับจุดยอดที่ดีสำหรับการระบายสีแบบโลภนั้นยาก การหาลำดับจุดยอดที่ไม่ดีก็ยากเช่นกัน การหาลำดับจุดยอดที่ไม่ดี สำหรับกราฟ Gและจำนวนk ที่กำหนด นั้น เป็นปัญหา NP-complete ซึ่งหมายความว่าการหาลำดับที่แย่ที่สุดสำหรับG นั้นยาก^{[ 12 ]}

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

หากสุ่มเลือกกราฟ จาก แบบจำลอง Erdős–Rényiด้วยความน่าจะเป็นคงที่ในการรวมขอบแต่ละขอบ การเรียงลำดับจุดยอดใดๆ ที่เลือกโดยอิสระจากขอบกราฟจะนำไปสู่การระบายสีที่มีจำนวนสีใกล้เคียงกับสองเท่าของค่าที่เหมาะสมที่สุดด้วยความน่าจะเป็นสูงยังไม่เป็นที่ทราบแน่ชัดว่ามีวิธีการในเวลาพหุนามใดๆ ที่สามารถค้นหาการระบายสีที่ดีกว่าอย่างมีนัยสำคัญสำหรับกราฟเหล่านี้หรือไม่^{[ 3 ]}

ปริซึมสามเหลี่ยมและแอนติปริซึมสี่เหลี่ยม กราฟที่การระบายสีแบบโลภโดยใช้ลำดับความเสื่อมให้จำนวนสีมากกว่าจำนวนสีที่เหมาะสม

เนื่องจากการหาลำดับจุดยอดที่เหมาะสมที่สุดนั้นทำได้ยาก จึง มีการใช้ ฮิวริสติกส์ที่พยายามลดจำนวนสีโดยไม่รับประกันจำนวนสีที่เหมาะสมที่สุด ลำดับที่ใช้กันทั่วไปสำหรับการระบายสีแบบโลภคือการเลือกจุดยอดv ที่มี ดีกรีต่ำสุดเรียงลำดับกราฟย่อยโดยลบv ออกแบบ เรียกซ้ำแล้ววางv ไว้ ท้ายสุดในลำดับ ดีกรีสูงสุดของจุดยอดที่ถูกลบออกที่อัลกอริทึมนี้พบเรียกว่าความเสื่อมของกราฟ ซึ่งแสดงด้วยdในบริบทของการระบายสีแบบโลภ กลยุทธ์การเรียงลำดับเดียวกันนี้ยังเรียกว่าการเรียงลำดับแบบเล็กที่สุดสุดท้าย^{[ 14 ]}การเรียงลำดับจุดยอดนี้และความเสื่อมสามารถคำนวณได้ในเวลาเชิงเส้น^{[ 15 ]} สามารถมองได้ว่าเป็นเวอร์ชันที่ได้รับการปรับปรุงของวิธีการเรียงลำดับจุดยอดก่อนหน้านี้ การเรียงลำดับแบบใหญ่ที่สุดก่อน ซึ่งเรียงลำดับจุดยอดจากมากไปน้อยตามดีกรี^{[ 16 ]}

ด้วยลำดับความเสื่อม การระบายสีแบบโลภจะใช้สีอย่างมากที่สุดd  + 1สี เนื่องจากเมื่อระบายสีแล้ว แต่ละจุดยอดจะมีเพื่อนบ้านที่ระบายสีแล้ว อย่างมากที่สุด d จุด ดังนั้นหนึ่งใน d  + 1สีแรกจะว่างให้ใช้งานได้^{[ 17 ]}การระบายสีแบบโลภด้วยลำดับความเสื่อมสามารถค้นหาการระบายสีที่เหมาะสมที่สุดสำหรับกราฟบางประเภท รวมถึงต้นไม้ ป่าเทียมและกราฟมงกุฎ^{[ 18 ]} Markossian, Gasparian & Reed (1996)กำหนดให้กราฟเป็น-perfect ถ้าสำหรับและกราฟย่อยที่เหนี่ยวนำทุกกราฟของจำนวนสีเท่ากับความเสื่อมบวกหนึ่ง สำหรับกราฟเหล่านี้ อัลกอริทึมแบบโลภด้วยลำดับความเสื่อมจะเหมาะสมที่สุดเสมอ^{[ 19 ]} กราฟที่สมบูรณ์แบบ ทุกกราฟต้องเป็นกราฟที่ไม่มีรูคู่เพราะวัฏจักรคู่มีจำนวนสีสองและความเสื่อมสอง ซึ่งไม่ตรงกับความเท่าเทียมกันในคำจำกัดความของกราฟที่สมบูรณ์แบบ หากกราฟและกราฟส่วนเติมเต็ม ของมัน ไม่มีรูคู่ทั้งคู่ กราฟทั้งสองก็จะเป็นกราฟที่สมบูรณ์แบบ กราฟที่เป็นทั้งกราฟที่สมบูรณ์แบบและกราฟที่สมบูรณ์แบบคือกราฟคอร์ดัล บนกราฟที่ไม่มีรูคู่โดยทั่วไป ลำดับความเสื่อมจะประมาณค่าการระบายสีที่เหมาะสมที่สุดได้ภายในไม่เกินสองเท่าของจำนวนสีที่เหมาะสมที่สุด นั่นคืออัตราส่วนการประมาณค่าคือ 2 ^{[ 20 ]}บนกราฟดิสก์หน่วยอัตราส่วนการประมาณค่าคือ 3 ^{[ 21 ]}ปริซึมสามเหลี่ยมเป็นกราฟที่เล็กที่สุดที่ลำดับความเสื่อมอย่างใดอย่างหนึ่งนำไปสู่การระบายสีที่ไม่เหมาะสม และแอนติปริซึมสี่เหลี่ยมเป็นกราฟที่เล็กที่สุดที่ไม่สามารถระบายสีได้อย่างเหมาะสมโดยใช้ลำดับความเสื่อมใดๆ ของมัน^{[ 18 ]}${\displaystyle G}$${\displaystyle \beta }$${\displaystyle G}$${\displaystyle G}$${\displaystyle \beta }$${\displaystyle \beta }$${\displaystyle \beta }$${\displaystyle \beta }$

Brélaz (1979)เสนอกลยุทธ์ที่เรียกว่าDSaturสำหรับการจัดลำดับจุดยอดในการระบายสีแบบโลภ (greedy coloring) ซึ่งสลับการสร้างลำดับกับกระบวนการระบายสี ในเวอร์ชันของอัลกอริทึมการระบายสีแบบโลภ จุดยอดถัดไปที่จะระบายสีในแต่ละขั้นตอนจะถูกเลือกเป็นจุดยอดที่มีจำนวนสีที่แตกต่างกันมากที่สุดในบริเวณใกล้เคียงในกรณีที่มีจำนวนสีเท่ากัน จุดยอดที่มีดีกรีสูงสุดในกราฟย่อยของจุดยอดที่ยังไม่ได้ระบายสีจะถูกเลือกจากจุดยอดที่มีดีกรีเท่ากัน โดยการติดตามเซตของสีที่อยู่ใกล้เคียงและจำนวนสมาชิกในแต่ละขั้นตอน ทำให้สามารถนำวิธีการนี้ไปใช้ในเวลาเชิงเส้นได้^{[ 22 ]}

วิธีนี้สามารถค้นหาการระบายสีที่เหมาะสมที่สุดสำหรับกราฟสองส่วน [ ^{23 ]}กราฟกระบองเพชรทั้งหมดกราฟวงล้อทั้งหมดกราฟทั้งหมดที่มีจุดยอดไม่เกินหกจุด และกราฟที่สามารถระบายสีได้^{เกือบ}ทุก กราฟ ^{[ 24 ]}แม้ว่าLévêque & Maffray (2005)จะอ้างว่าวิธีนี้ค้นหาการระบายสีที่เหมาะสมที่สุดสำหรับกราฟ Meynielแต่ต่อมาพวกเขาก็พบตัวอย่างค้านต่อข้ออ้างนี้^{[ 25 ]}${\displaystyle k}$

สามารถกำหนดรูปแบบต่างๆ ของอัลกอริทึมการระบายสีแบบโลภ (greedy coloring algorithm) ได้ โดยที่จุดยอดของกราฟที่กำหนดจะถูกระบายสีตามลำดับที่กำหนด แต่สีที่เลือกสำหรับแต่ละจุดยอดนั้นไม่จำเป็นต้องเป็นสีแรกที่มีให้เลือกเสมอไป วิธีการเหล่านี้รวมถึงวิธีการที่ส่วนที่ยังไม่ได้ระบายสีของกราฟนั้นไม่เป็นที่รู้จักสำหรับอัลกอริทึม หรือวิธีการที่อัลกอริทึมได้รับอิสระในการเลือกสีที่ดีกว่าอัลกอริทึมแบบโลภพื้นฐาน

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

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

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

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

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

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