圖譜著色?是圖譜標(biāo)記的一個(gè)特例；它是對(duì)圖譜中的元素進(jìn)行傳統(tǒng)上稱為顏色的標(biāo)簽分配，并受到某些約束。在其最簡(jiǎn)單的形式中，它是一種為圖的頂點(diǎn)著色的方法，使相鄰的兩個(gè)頂點(diǎn)不具有相同的顏色；這被稱為頂點(diǎn)著色。同樣，邊著色為每條邊分配顏色，使相鄰的兩條邊不具有相同的顏色，而平面圖的面著色為每個(gè)面或區(qū)域分配顏色，使共享邊界的兩個(gè)面不具有相同的顏色。頂點(diǎn)著色經(jīng)常被用來(lái)介紹圖形著色問(wèn)題，因?yàn)槠渌珕?wèn)題可以轉(zhuǎn)化為頂點(diǎn)著色實(shí)例。

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

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

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