Secara umum, untuk sembarang graf \(G\text{,}\) pemberian warna pada simpul-simpulnya disebut (tidak mengherankan) pewarnaan simpul. Jika dalam pewarnaan simpul tersebut simpul-simpul yang bertetangga diberi warna berbeda, pewarnaan itu disebut tepat. Setiap graf memiliki pewarnaan simpul yang tepat. Sebagai contoh, Anda dapat memberi setiap simpul warna yang berbeda. Namun, sering kali kita dapat menggunakan lebih sedikit warna. Jumlah warna minimum yang diperlukan untuk memperoleh pewarnaan simpul yang tepat disebut bilangan kromatik graf tersebut, yang ditulis \(\chi(G)\text{.}\)