Pewarnaan graf (graph coloring) adalah kasus khusus dari pelabelan graf. Pelabelan disini maksudnya, yaitu memberikan warna pada titik-titik pada batas tertentu. Ada tiga macam pewarnaan graf :
1. Pewarnaan simpul
Pewarnaan simpul (vertex coloring) adalah member warna pada simpul-simpul suatu graf sedemikian sehingga tidak ada dua simpul bertetangga mempunyai warna yang sama.
Gambar 4. Contoh pewarnaan simpul
2. Pewarnaan sisi
Pewarnaan sisi (edge coloring) adalah memberi warnaberbeda pada sisi yang bertetangga sehingga tidak ada dua sisi yang bertetangga mempunyai warna yang sama.
Gambar 5. Contoh pewarnaan sisi
3. Pewarnaan bidang
Pewarnaan bidang adalah memberi warna pada bidang sehingga tidak ada bidang yang bertetangga mempunyai warna yang sama. Pewarnaan bidang hanya bisa dilakukan dengan membuat graf tersebut menjadi graf planar terlebih dahulu. Graf planar adalah graf yang dapat digambarkan pada bidang datar dengan sisi-sisi yang tidak saling memotong (bersilangan), seperti yang ditunjukkan gambar di bawah ini.
Gambar 6. Contoh Grraf Planar
Setelah terbentuk graf planar, lalu memberikan warna berbeda untuk setiap bidang yang berdekatan. Dan jumlah warna yang digunakan harus sedikit mungkin.
Gambar 7. Contoh pewarnaan bidang
Dalam pewarnaan graf, jumlah warna yang digunakan untuk mewarnai simpul, sisi, maupun bidang diusahakan sesedikit mungkin. Jumlah warna minimum yang dapat digunakan tersebut disebut bilangan kromatik graf G, disimbolkan dengan χ(G). Suatu graf G yang mempunyai bilangan kromatis k dilambangkan dengan χ(G) = k.
PENGATURAN WARNA PADA LAMPU LALU LINTAS MENGGUNAKAN GRAF
Sudah disebutkan sebelumnya bahwa sampai saat ini, teori graf masih diterapkan di berbagai persoalan dalam kehidupan sehari-hari. Misalnya aplikasi pewarnaan graf dalam pengaturan warna lampu lalu lintas di perempatan jalan sehingga mencegah terjadinya tabrakan di perempatan jalan tersebut
Gambar 8. Lampu lalu lintas perempatan jalan
Seperti yang ditunjukkan pada gambar diatas, sebuah perempatan jalan mempunyai 4 buah lampu lalu lintas. Lampu lalu lintas pada jalan B dan F menyala bersamaan. Lampu lalu lintas pada jalan D dan H juga menyala bersamaan. Dalam perempatan jalan tersebut diketahui jika lampu di jalan B dan F menyala hijau maka jalur yang boleh digunakan adalah dari B ke E, F ke A. selain itu jalur langsung belok kiri juga diperbolehkan, yaitu dari B ke C, dan F ke G. Jika di jalan D dan H lampu hijau menyala maka jalur yang boleh digunakan untuk melintas adalah jalur dari D ke E, D ke G, H ke A, dan H ke C. Dalam kondisi ini, jalur langsung belok kiri juga diperoblehkan. Untuk menyelesaikan permasalahan pada pembuatan lampu lalu lintas pada sebuah perempatan jalan, maka hal yang harus dilakukan terlebih dahulu adalah menentukan jalur mana yang bisa berjalan dengan member lampu hijau di tempat tertentu dan member lampu merah agar kendaraan pada lintasan yang lain berhenti sehingga tidak terjadi tabrakan.