Definíció: Egy gráf (csúcs) színezései: A csúcsokon értelmezett P-be (a pozitív egészekbe) képező függvény.
P-re mint piros, kék, zöld, ... színek halmazára kell gondolnunk.
Definíció: Egy gráf jó színezése: egy olyan színezés, amely összekötött csúcsknak különböző színt ad.
Megjegyzés: Egy gráfnak akkor és csak akkor van jó színezése ha nem tartalmaz hurokélt, hiszen ekkor az összes pontnak különböző színt adva jó színezést kapunk más esetben, viszont a hurokél két, egybeeső végpontját nem tudjuk különböző színűre festeni.
Megjegyzés: Egy gráf színezésénél két csúcsra tekintve csak az számít, hogy össze vannak-e kötve vagy nem. Az összekötöttség multiplicitása lényegtelen.
A TOVÁBBIAKBVAN SZÍNEZÉSEK ESETÉN MINDEN VIZSGÁLT GRÁFRÓL FELTESSZÜK, HOGY EGYSZERŰ.
Definíció: Egy gráf kromatikus száma: a minimális k, amelyre G-nek van k színnel történő jó színezése.
Példa: Dodekaédergráf 3-színezése
Példa: Kockagráf 2-színezése
Példa: Petersen-gráf 3-színezése
Egy gráf egy színnel történő színezhetőségét pontosan egy él léte akadályozza meg.
Tétel: Egy gráf két színnel történő színezhetőségét pontosan egy páratlan kör akadályozza meg.
Bizonyítás: Az állítás "nehéz" része az, hogy egy páratlan kör nélküli gráf jól színezhető két színnel. Feltehető, hogy G összefüggő (miért?). Legyen T a G gráf egy feszítőfája. T-nek van jó 2-színezése (miért?). T és G csúcshalmaza azonos, azaz az előző jó színezés G egy színezését is adja. Belátjuk, hogy (meglepő módon) ez G-nek is jó színezése lesz, azaz tetszőleges G-beli él két végpontja különböző színt kap. Ez T-beli élek esetén nyilvánvaló. Ha e egy nem T-beli él, akkor T feszítőfa volta miatt találhatunk egy C kört G-ben, ami tartalmazza e-t és minden más éle T-beli (e alapköre T-re vonatkozólag). Feltételünk szerint C egy páros élt tartalmazó kör. T-t színezésünk jól színezi. Ebből könnyű kikövetkeztetni, hogy e két végpontja különböző színt fog kapni.
A színezési kérdések a gráfelmélet nagyon fontos kérdéskörét alkotják. Az alábbiakban néhány interneten is elérhető forrást említünk.
