ในทฤษฎีกราฟซึ่งเป็นสาขาหนึ่งของคณิตศาสตร์การระบายสีแบบลิสต์เป็นประเภทหนึ่งของการระบายสีกราฟโดยที่แต่ละจุดยอดสามารถจำกัดให้ใช้สีตามลิสต์ที่อนุญาตได้ มีการศึกษาครั้งแรกในช่วงทศวรรษ 1970 ในบทความอิสระของVizing และErdős , Rubinและ Taylor ^{[ 1 ]}

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

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

พิจารณากราฟสองส่วน สมบูรณ์ G = K _2,4ซึ่งมีจุดยอดหกจุดA , B , W , X , Y , Zโดยที่AและBเชื่อมต่อกับW , X , YและZ ทั้งหมด และไม่มีจุดยอดอื่นใดเชื่อมต่อกัน เนื่องจากเป็นกราฟสองส่วนGจึงมีจำนวนสีปกติเท่ากับ 2 กล่าวคือ เราสามารถระบายสีAและBด้วยสีหนึ่ง และระบายสีW , X , Y , Zด้วยอีกสีหนึ่ง และไม่มีจุดยอดที่อยู่ติดกันสองจุดใดที่มีสีเดียวกัน ในทางกลับกันGมีจำนวนสีแบบลิสต์มากกว่า 2 ดังที่การสร้างต่อไปนี้แสดงให้เห็น: กำหนดลิสต์ {แดง, น้ำเงิน} และ {เขียว, ดำ} ให้กับAและBและกำหนดลิสต์ {แดง, เขียว}, {แดง, ดำ}, {น้ำเงิน, เขียว} และ {น้ำเงิน, ดำ} ให้กับจุดยอดอีกสี่จุด ไม่ว่าเราจะเลือกสีใดจากรายการสีAและสีใดจากรายการสีBก็จะมีจุดยอดอื่นที่สีทั้งสองที่เลือกไว้นั้นถูกใช้ไปแล้วในการระบายสีจุดยอดข้างเคียง ดังนั้นGจึงไม่ใช่กราฟที่เลือกได้ 2 สี

ในทางกลับกัน ก็เห็นได้ง่ายว่าGสามารถเลือกได้ 3 แบบ: การเลือกสีใดๆ สำหรับจุดยอดAและBจะเหลือสีอย่างน้อยหนึ่งสีสำหรับจุดยอดที่เหลือแต่ละจุด และสีเหล่านี้สามารถเลือกได้ตามอำเภอใจ

โดยทั่วไปแล้ว ให้qเป็นจำนวนเต็มบวก และให้Gเป็นกราฟสองส่วนสมบูรณ์K = _{q, q₁, q₂, ^...} , qₙ ให้สีที่มีอยู่แทนด้วยจำนวนสองหลักที่แตกต่างกันq จำนวน ² จำนวน ใน ฐานqด้านหนึ่งของการแบ่งสองส่วน ให้ จุดยอด qจุด เป็นเซตของสี{ i₀ , i₁ , i₂ , ... } ซึ่งหลักแรกของตัวเลขแต่ละหลักเท่ากัน สำหรับแต่ละ ตัวเลือกที่เป็นไปได้ qตัวของหลักแรก  iอีกด้านหนึ่งของการแบ่งสองส่วน ให้ จุดยอด q ^จุดเป็นเซตของสี{0, a , 1, b , 2, c , ... } ซึ่งหลักแรกของตัวเลขแต่ละหลักแตกต่างกัน สำหรับแต่ละตัวเลือกที่เป็นไปได้q ^ตัว ของ คู่( a , b , c , ...)ภาพประกอบ แสดงตัวอย่างที่ใหญ่กว่าของโครงสร้างเดียวกัน โดยที่q = 3

จากนั้นGไม่มีรายการการระบายสีสำหรับL : ไม่ว่าชุดสีใดจะถูกเลือกสำหรับจุดยอดด้านเล็กของการแบ่งสองส่วน การเลือกนี้จะขัดแย้งกับสีทั้งหมดสำหรับจุดยอดหนึ่งจุดบนอีกด้านหนึ่งของการแบ่งสองส่วน ตัวอย่างเช่น หากจุดยอดที่มีชุดสี {00,01} ถูกระบายสีเป็น 01 และจุดยอดที่มีชุดสี {10,11} ถูกระบายสีเป็น 10 จุดยอดที่มีชุดสี {01,10} จะไม่สามารถระบายสีได้ ดังนั้นจำนวนสีโครมาติกของGจึงมีอย่างน้อยq + 1 ^{[ 2 ]}

ในทำนองเดียวกัน หากกราฟสองส่วนสมบูรณ์K _n,nไม่ สามารถเลือกได้ k สี สมมติว่ามีสีทั้งหมด2 k − 1 สี และในแต่ละด้านของการแบ่งสองส่วน แต่ละจุดยอดจะมี k -tuple ของสีที่แตกต่างกันจากจุดยอดอื่นๆ ดังนั้นแต่ละด้านของการแบ่งสองส่วนจะต้องใช้สีอย่างน้อยkสี เนื่องจากชุดสีk − 1สีแต่ละชุดจะไม่ซ้ำกับรายการของจุดยอดหนึ่งจุด เนื่องจากมีการใช้สีอย่างน้อยkสีในด้านหนึ่งและอย่างน้อยkสีในอีกด้านหนึ่ง จึงต้องมีสีหนึ่งสีที่ใช้ในทั้งสองด้าน แต่นั่นหมายความว่าจุดยอดที่อยู่ติดกันสองจุดจะมีสีเดียวกัน โดยเฉพาะอย่างยิ่งกราฟยูทิลิตี้K _3,3มีจำนวนสีในรายการอย่างน้อยสาม และกราฟK _10,10มีจำนวนสีในรายการอย่างน้อยสี่^{[ 3 ]}${\displaystyle n={\tbinom {2k-1}{k}},}$

สำหรับกราฟGให้χ ( G )แทนจำนวนสีที่ใช้ในการระบายสี และΔ( G )แทนดีกรีสูงสุดของGจำนวนการระบายสีแบบลิสต์ch( G )มีคุณสมบัติดังต่อไปนี้

1. ch( G ) ≥ χ ( G )กราฟ ที่สามารถระบายสีด้วยลิสต์ k สีได้นั้น จะต้องมีการระบายสีด้วยลิสต์ โดยที่ทุกจุดยอดจะได้รับลิสต์สี k สี เดียวกัน ซึ่งสอดคล้องกับ การระบายสีk สี แบบปกติ
2. ch( G )ไม่สามารถจำกัดได้ในแง่ของจำนวนสีโดยทั่วไป นั่นคือ ไม่มีฟังก์ชันfใดที่ch( G ) ≤ f ( χ ( G ))เป็นจริงสำหรับกราฟG ทุกกราฟ โดยเฉพาะอย่างยิ่ง ดังที่ตัวอย่างกราฟสองส่วนสมบูรณ์แสดงให้เห็น มีกราฟที่มีχ ( G ) = 2แต่มีch( G )มากตามอำเภอใจ^{[ 2 ]}
3. ch( G ) ≤ χ ( G ) ln( n )โดยที่nคือจำนวนจุดยอดของG ^{[ 4 ] [ 5 ]}
4. ch( G ) ≤ Δ( G ) + 1 . ^{[ 3 ] [ 6 ]}
5. ch( G ) ≤ 5ถ้าGเป็นกราฟระนาบ^{[ 7 ]}
6. ch( G ) ≤ 3ถ้าGเป็นกราฟระนาบสองส่วน^{[ 8 ]}

ในเอกสารทางวิชาการได้พิจารณาปัญหาเชิงอัลกอริทึมสองประการ ได้แก่:

1. k - choosability : ตัดสินใจว่ากราฟที่กำหนดนั้น สามารถเลือกได้ kแบบหรือไม่ สำหรับค่าk ที่กำหนด และ
2. ( a , b ) - ความสามารถในการเลือก : ตัดสินใจว่ากราฟที่กำหนดนั้นสามารถเลือกได้ด้วยฟังก์ชันf หรือไม่${\displaystyle f:V\to \{a,\dots ,b\}}$

เป็นที่ทราบกันว่าk- choosability ในกราฟสองส่วนเป็น-complete สำหรับk ≥ 3 ใดๆ และเช่นเดียวกันนี้ใช้ได้กับ 4-choosability ในกราฟระนาบ 3-choosability ในกราฟระนาบที่ไม่มีสามเหลี่ยมและ (2, 3)-choosability ในกราฟระนาบสองส่วน^{[ 9 ] [ 10 ]}สำหรับ กราฟ P ₅ -free นั่นคือกราฟที่ไม่รวมกราฟเส้นทาง 5 จุดยอดk - choosability สามารถจัดการได้ด้วยพารามิเตอร์คงที่ ^{[ 11 ]}${\displaystyle \Pi _{2}^{p}}$

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

การระบายสีรายการเกิดขึ้นในปัญหาเชิงปฏิบัติเกี่ยวกับการกำหนดช่องสัญญาณ/ความถี่^{[ 12 ] [ 13 ]}

ลองค้นหาคำว่า choosabilityใน Wiktionary ซึ่งเป็นพจนานุกรมออนไลน์ฟรี

• การระบายสีขอบรายการ