26/08/2025
ชื่องาน: The Total Choosability with Neighbor Sum Distinguishing Properties of Planar Graphs That Are Devoid of C_5 Adjacent to C_3
ผู้เขียนที่เป็นสมาชิก SimBioSen: ดร. พงษ์พัฒน์ สิทธิไตรย์
วาสารชื่อ: The European Journal of Pure and Applied Mathematics
การระบายสีแบบ Total Choosability with Neighbor Sum Distinguishing มีความซับซ้อนสูง เนื่องจากต้องใช้การเลือกสีจากชุดสีที่กำหนดให้สำหรับทั้งจุดยอดและเส้นเชื่อมในกราฟ ซึ่งการระบายสีแบบนี้ประกอบด้วย 3 คุณสมบัติหลัก ได้แก่ Total Coloring, List Coloring, และ Neighbor Sum Distinguishing ซึ่งจะอธิบายดังนี้:
1. Total Coloring: ปกติการระบายสีที่พบมากคือการระบายสีจุดยอดหรือการระบายสีเส้นเชื่อมแยกกัน แต่ในกรณีของ Total Coloring จะเป็นการระบายสีทั้งจุดยอดและเส้นเชื่อมในกราฟ โดยที่จุดยอดหรือเส้นเชื่อมที่เชื่อมติดกันจะต้องได้รับสีที่แตกต่างกัน
2. List Coloring: เป็นการขยายแนวคิดของการระบายสีกราฟที่ใช้ชุดสีสำหรับแต่ละจุดยอดในกราฟ โดยแต่ละจุดยอดจะมีชุดสีที่สามารถเลือกได้ ซึ่งอาจเหมือนกันหรือแตกต่างกัน สำหรับการระบายสีแบบปกติ เราจะใช้ชุดสีเดียวกันในการระบาย แต่ใน List Coloring จะให้ความยืดหยุ่นในการเลือกสีให้กับจุดยอดแต่ละจุด
3. Neighbor Sum Distinguishing: การระบายสีกราฟแบบ Neighbor Sum Distinguishing ต้องให้ผลรวมของสีที่เลือกให้กับจุดยอดที่เชื่อมต่อกับจุดยอดและเส้นเชื่อมที่ติดกันนั้นมีค่าแตกต่างกันในกราฟที่ได้รับการระบายสี
ในงานวิจัยนี้ ผู้แต่งได้แสดงให้เห็นว่า กราฟเชิงระนาบ ที่ไม่มีวงจรขนาด 5 ที่ติดกับวงจรขนาด 3 จะสามารถระบายสีในรูปแบบ Total Choosability with Neighbor Sum Distinguishing โดยใช้จำนวนสีที่มากขึ้น ซึ่งจะมีจำนวนสีที่ มากกว่าค่าดีกรีสูงสุด (maximum degree) บวกสาม หรือเปรียบเทียบกับ 10 เสมอ