ปัญหาที่ยังแก้ไม่ได้ในวิชาคณิตศาสตร์

ข้อสันนิษฐาน:${\displaystyle \chi ''(G)\leq \Delta (G)+2.}$

ปัญหาที่ยังแก้ไม่ตกในวิชาคณิตศาสตร์ยังมีอีกมากมาย

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

กราฟทั้งหมดT = T ( G )ของกราฟGคือกราฟที่มีคุณสมบัติว่า (i) เซตของจุดยอดของTสอดคล้องกับจุดยอดและขอบของGและ (ii) จุดยอดสองจุดอยู่ติดกันในTก็ต่อเมื่อสมาชิกที่สอดคล้องกันของจุดยอดทั้งสองนั้นอยู่ติดกันหรือเชื่อมต่อกันในGดังนั้น การระบายสีทั้งหมดของGจึงกลายเป็นการระบายสีจุดยอด (ที่เหมาะสม)ของT ( G )การระบายสีทั้งหมดคือการแบ่งจุดยอดและขอบของกราฟออกเป็นเซต อิสระทั้งหมด

อสมการบางประการสำหรับχ ″( G ) :

1. ${\displaystyle \chi ''(G)\geq \Delta (G)+1.}$
2. ${\displaystyle \chi ''(G)\leq \Delta (G)+10^{26}.}$ (มอลลอย, รีด 1998)
3. ${\displaystyle \chi ''(G)\leq \Delta (G)+8\ln ^{8}(\Delta (G))}$สำหรับΔ( G ) ที่มีขนาดใหญ่พอสมควร (Hind, Molloy, Reed 1998)
4. ${\displaystyle \chi ''(G)\leq \operatorname {ch} '(G)+2.}$

ในที่นี้Δ( G )คือระดับสูงสุดและch′( G )คือ ความสามารถ ใน การเลือกขอบ

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

การหาขอบเขตบนของดีกรีสูงสุดโดยใช้การระบายสีทั้งหมดเป็นปัญหาที่ยากซึ่งนักคณิตศาสตร์ยังหาคำตอบไม่ได้มานานกว่า 50 ปีแล้ว ขอบเขตล่างที่ไม่สำคัญสำหรับχ ″( G )คือΔ( G ) + 1กราฟบางประเภท เช่น วัฏจักรที่มีความยาวและกราฟสองส่วนสมบูรณ์ในรูปแบบK _n,nต้องการ สี Δ( G ) + 2สี แต่ยังไม่พบกราฟใดที่ต้องการสีมากกว่านี้ สิ่งนี้ทำให้เกิดการคาดการณ์ว่ากราฟทุกกราฟต้องการสีΔ( G ) + 1หรือΔ( G ) + 2สี แต่ไม่เคยมากกว่านั้น ${\displaystyle n\not \equiv 0{\bmod {3}}}$

สมมติฐานการระบายสีทั้งหมด ( เบห์ซาด , วิซิง)${\displaystyle \chi ''(G)\leq \Delta (G)+2.}$

ปรากฏว่า คำว่า "การระบายสีทั้งหมด" และข้อความของสมมติฐานการระบายสีทั้งหมดนั้น ถูกนำเสนอโดยอิสระโดยBehzadและVizingในหลายโอกาสระหว่างปี 1964 ถึง 1968 (ดู Jensen & Toft) สมมติฐานนี้เป็นที่ทราบกันว่าใช้ได้กับกราฟบางประเภทที่สำคัญ เช่นกราฟสองส่วน ทั้งหมด และกราฟระนาบ ส่วนใหญ่ ยกเว้นกราฟที่มีดีกรีสูงสุด 6 กรณีของกราฟระนาบจะสมบูรณ์ได้หากสมมติฐานกราฟระนาบของ Vizingเป็นจริง นอกจากนี้ หากสมมติฐานการระบายสีรายการเป็นจริงแล้ว${\displaystyle \chi ''(G)\leq \Delta (G)+3.}$

ผลลัพธ์ที่เกี่ยวข้องกับการระบายสีทั้งหมดได้รับการค้นพบแล้ว ตัวอย่างเช่น Kilakos และ Reed (1993) พิสูจน์ว่าจำนวนสีเศษส่วนของกราฟทั้งหมดของกราฟGมีค่าไม่เกินΔ( G ) + 2