Klasyczne kolorowanie grafu - to przyporządkowywanie wierzchołkom grafu liczb naturalnych w taki sposób, aby końce żadej krawędzi nie miały przypisanej tej samej liczby. Dla lepszego zobrazowania problemu mówi się o kolorowaniu, przy czym różnym kolorom odpowiadają różne liczby.
Pokolorowaniem wierzchołków grafu nazywamy jedno konkretne przyporządkowanie liczb (kolorów) wierzchołkom.
Pokolorowanie jest legalne (dozwolone) gdy końcom żadnej krawędzi nie przyporządkowano tej samej liczby (koloru).
Optymalnym pokolorowaniem grafu nazywamy legalne pokolorowanie zawierające najmniejszą możliwą liczbę kolorów.
Liczbą chromatyczną grafu G nazywamy liczbę \[\chi(G) \] równą minimalnej liczbę kolorów wystarczającej do prawidłowego pokolorowania wierzchołków grafu G.
Ze względu na bardzo szerokie zastosowania kolorowanie grafów jest przedmiotem rozległych badań. Niestety, problem znalezienia optymalnego pokolorowania a także znalezienia liczby chromatycznej jest NP zupełny.
Kolorowanie grafów ma wiele odmian:
  • Kolorowanie krawędzi
  • Sprawiedliwe kolorowanie
  • Sumacyjne kolorowanie
  • Kontrastowe kolorowanie
  • Harmoniczne kolorowanie
  • Cyrkularne kolorowanie
Publikacja wraz ze zdjęciami jest udostępniona w Encyklopedii "Zgapedia" części portalu zgapa.pl. Treść objęta jest licencją GNU FDL Wolnej Dokumentacji w wersji 1.3 lub dowolnej pózniejszej opublikowanej przez Free Software Foundation i została ona opracowana na podstawie Wikipedii, tutaj możesz znaleźć artykuł źródłowy oraz autorów. Warunki użytkowania Encyklopedii znajdziesz na tej stronie.