ปัญหาการให้สีกราฟแบบแบ็คโบน

บทคัดย่อ

กําหนดให้ H เป็นกราฟย่อยของกราฟ G ในคู่อันดับของกราฟ (G,H) การให้สีกราฟแบบแบ็คโบนของคู่อันดับของกราฟ (G,H) คือ การให้สีจุดยอดของกราฟ G โดยแต่ละจุดยอดที่ประชิดกันมีค่าสีแตกต่างกัน โดยเพิ่มเงื่อนไขจุดยอดที่ประชิดกันในกราฟย่อย H ต้องมีค่าสี แตกต่างกันอย่างน้อยที่สุด 2
ในบทความนี้นําเสนอที่มาของการศึกษาปัญหาการให้สีกราฟแบบแบ็คโบนอย่างสังเขปและการให้สีกราฟแบบอื่นๆ ที่เกี่ยวข้อง หลังจากนั้นจะกล่าวถึงงานวิจัยที่เกี่ยวข้องกับปัญหาการให้สีกราฟแบบแบ็คโบน เช่น การกําหนดแบบ L(2,1) การให้สีกราฟแบบ  λ-แบ็คโบนและการให้สีกราฟแบบลิสต์แบ็คโบน อีกทั้งยังนําเสนอหัวข้องานวิจัยในอนาคต