圖譜著色

圖譜著色?是圖譜標記的一個特例；它是對圖譜中的元素進行傳統上稱為顏色的標簽分配，并受到某些約束。在其最簡單的形式中，它是一種為圖的頂點著色的方法，使相鄰的兩個頂點不具有相同的顏色；這被稱為頂點著色。同樣，邊著色為每條邊分配顏色，使相鄰的兩條邊不具有相同的顏色，而平面圖的面著色為每個面或區域分配顏色，使共享邊界的兩個面不具有相同的顏色。頂點著色經常被用來介紹圖形著色問題，因為其他著色問題可以轉化為頂點著色實例。

圖形著色的第一個結果幾乎只涉及平面圖形的地圖著色。在試圖為英格蘭各郡的地圖著色時，弗朗西斯-格思里提出了四色猜想，指出四種顏色足以為地圖著色，從而使具有共同邊界的區域都不會得到相同的顏色。格思里的弟弟將這個問題傳給了他在大學學院的數學老師奧古斯都-德-摩根，后者在1852年給威廉-漢密爾頓的信中提到了這個問題。阿瑟-凱利在1879年倫敦數學會的一次會議上提出了這個問題。同年，阿爾弗雷德-肯普（AlfredKempe）發表了一篇論文，聲稱確立了這一結果，十年來，四色問題被認為已經解決。由于他的成就，肯普被選為皇家學會會員，后來又被選為倫敦數學學會主席。1890年，海伍德指出肯普的論點是錯誤的。然而，在那篇論文中，他證明了五色定理，說每個平面圖都可以用不超過五種顏色來著色，使用的是肯普的想法。在接下來的一個世紀里，大量的工作和理論被開發出來，以將顏色的數量減少到四種，直到四色定理最終在1976年被KennethAppel和WolfgangHaken證明。該證明回到了Heawood和Kempe的想法，并在很大程度上無視了中間的發展。四色定理的證明還值得一提的是，它是第一個重要的計算機輔助證明。1912年，喬治-大衛-伯克霍夫引入色度多項式來研究著色問題，被圖特概括為圖特多項式，是代數圖論的重要結構。

Kempe在1879年已經引起了對一般的、非平面的情況的注意，在20世紀初，許多關于平面圖著色對高階表面的泛化的結果也隨之而來。1960年，ClaudeBerge提出了另一個關于圖形著色的猜想，即強完美圖形猜想，最初的動機是香農提出的一個稱為圖形零誤差容量的信息論概念。這個猜想40年來一直沒有得到解決，直到2002年被Chudnovsky、Robertson、Seymour和Thomas確立為著名的強完美圖定理。自20世紀70年代初以來，圖形著色一直被作為一個算法問題來研究：色度數問題（見下文）是Karp在1972年提出的21個NP-complete問題之一，大約在同一時期，基于回溯和Zykov（1949）的刪除-收縮遞歸的各種指數時間算法被開發出來。圖著色的主要應用之一，即編譯器中的寄存器分配，于1981年被引入。

一個圖的邊著色只是其線圖的一個頂點著色，而一個平面圖的面著色只是其對偶的一個頂點著色。然而，非頂點著色問題往往是按原樣陳述和研究的。這一方面是教學上的原因，另一方面是因為有些問題最好以非頂點形式來研究，如邊緣著色的情況。使用顏色的慣例起源于為地圖的國家著色，其中每個面都是字面上的顏色。這被概括為對嵌入平面的圖形的面進行著色。通過平面二重性，它變成了給頂點著色，而在這種形式下，它可以推廣到所有的圖形。在數學和計算機表示中，典型的做法是使用前幾個正整數或非負整數作為顏色。一般來說，人們可以使用任何有限集作為顏色集。著色問題的性質取決于顏色的數量，但不取決于它們是什么。圖譜著色享有許多實際應用和理論上的挑戰。除了經典的問題類型外，還可以對圖形、分配顏色的方式、甚至是顏色本身設置不同的限制。它甚至以流行的數字謎題"數獨"的形式在公眾中流行起來。圖形著色仍然是一個非常活躍的研究領域。