Pewarnaan graf merupakan salah satu penerapan teori graf yang bertujuan untuk memberikan warna pada simpul atau sisi dengan ketentuan bahwa simpul atau sisi yang saling bertetangga tidak boleh memiliki warna yang sama. Salah satu bentuk penerapannya adalah pewarnaan wilayah pada peta, agar wilayah yang berbatasan dapat dibedakan secara visual. Penelitian ini bertujuan untuk membandingkan efektivitas Algoritma Greedy dan Algoritma Welch-Powell dalam menentukan jumlah warna minimum (bilangan kromatik) pada pewarnaan peta kabupaten di Pulau Kalimantan. Peta direpresentasikan ke dalam graf planar dan dilanjutkan dengan pembentukan graf dual sebagai dasar pewarnaan. Kedua algoritma diterapkan untuk melakukan proses pewarnaan simpul dengan metode masing-masing sesuai prinsip kerja algoritma tersebut. Hasil penelitian menunjukkan bahwa baik Algoritma Greedy maupun Algoritma Welch-Powell mampu menghasilkan pewarnaan yang memenuhi Teorema Empat Warna dan dapat memberikan solusi optimal, meskipun hasil akhir tetap bergantung pada proses penentuan simpul yang digunakan dalam pewarnaan.