1、山東科技大學碩士學位論文若干圖類的著色問題姓名：段華申請學位級別：碩士專業(yè)：運籌學與控制論指導教師：陳東靈2002.5.1碩士學位論文第一章序言圖的著色理論起源于150年前的“四色問題”或“四色猜想”。百余年來大批優(yōu)秀數(shù)學家為解決這個猜想花費了大量的心血，盡管迄今仍沒有得到非計算機的理論性證明，但人們在沖擊“四色猜想”時所采用的思想、方法和技巧為圖論寶庫增添了一個又一個精彩結果，致使圖的著色理論發(fā)展成為一個有廣泛實際應用和旺盛生命力的新

2、學科。1976年KAppel和WHaken在JKoch的協(xié)助下用計算機檢驗了“四色猜想”是正確的?！?，從而“四色猜想”為“四色定理”所代替。在1997年，NRobertson，DSanders和RThomast21給出“四色定理”的一個簡化的計算機證明。這當然是一個第一流的成就，但它在數(shù)學上和哲學上都引出許多新的問題，對許多數(shù)學家來說這個解決辦法并不是令人滿意的。離散系統(tǒng)中的許多問題表面上似乎與著色沒聯(lián)系，但最終要解決它們往往依賴于一個