基本介紹
- 中文名：與Steinberg猜想、全染色猜想相關的若干問題
- 項目類別：面上項目
- 項目負責人：王應前
- 依託單位：浙江師範大學
項目摘要,結題摘要,
項目摘要
主要研究兩個問題：（1）使得既沒有4-圈又沒有i-圈的平面圖是3可染地正整數i＞4所形成的集合I是否為空集（2）可平面圖的最大度加1的全可染性。前一問題與長期懸而未決的Steinberg猜想5屬於I有關；後一問題考慮全染色猜想（每個簡單圖是最大度加2全可染）在平面圖類內是否成立及比猜想更強的結論是否成立的問題。此外還研究相關列表染色、非正常染色等問題。列表染色和非正常染色是通常正常染色在兩種不同意義下自然而又更為普遍推廣， 已得到廣泛研究。對它們深入研究，可為研究尚未解決的有關正常染色的猜想提供更廣闊的視野和研究空間。主要在前人研究基礎上, 對問題的極小反例，進行大範圍地更深刻地結構分析，力求在結構組合分析技巧系統化方面和權轉移方法上推陳出新。計畫4年內在SCI源期刊上發表學術論文20餘篇。
結題摘要
圍繞圖染色理論中兩個著名猜想，即Steinberg猜想和全染色猜想，展開研究。Steinberg於1976年猜想：沒有4-圈和5-圈的平面圖是3色可染的。全染色猜想為Vizing（1964）和Behzad（1965）相互獨立提出：每個簡單圖是最大度加2全可染的。這兩個猜想被Bondy和Murty列為當今圖論中100個尚未解決的重要問題中的第53個和第61個問題。前者還在Open Problem Garden 中被列為6個4星級（最高級）問題之一。後者後來引申出許多著名的新猜想，如列表全染色猜想，完備染色猜想等。本項目提出並研究比Steinberg猜想更為一般的一個問題，可稱之為Post Steinberg Problem, 縮寫為PSP, 即使得沒有4-圈和i-圈（i＞4）的平面圖是3色可染的正整數i所形成的集合I是什麼，最近，Steinberg猜想已被Cohen-Addad等人所否定，這表明PSP是一個具有深遠影響且極具挑戰性的問題。由於已經知道沒有4-，i-，j-, k-圈4
