Pewarnaan peta adalah pemberian warna yang berbeda untuk dua daerah yang bertetangga dengan warna yang berbeda

Suatu pewarnaan sisi-k untuk graf g adalah suatu penggunaan sebagian atau semua k warna untuk mewarnai semua sisi di G sehingga setiap pasang sisi yang mempunyai titik persekutuan diberi warna yang berbeda. Jika G mempunyai pewarnaan sisi-k, maka dikatakan sisi-sisi di G diwarnai dengan k warna

Pewarnaan titik dari graf G adalah sebuah pemetaan warna-warna ke titik-titik dari G sedemikian hingga titik yang terhubung langsung mempunyai warna-warna yang berbeda. Graf G berwarna n jika terdapat sebuah pewarnaan dari G yang menggunakan n warna
Dalam pewarnaan titik erat kaitannya dengan penentuan bilangan kromatik, yaitu masalah menentukan banyak warna minimum yang diperlukan untuk mewarnai titik-titik pada graf sehingga dua titik yang terhubung langsung mempunyai warna yang berbeda

Graf Bunga adalah graf yang diperoleh dari graf helm dengan menghubungkan tiap-tiap titik anting-anting ke titik pusat dari graf Helm

Graf Helm Tertutup adalah graf yang diperoleh dari sebuah graf Helm dengan menghubungkan tiap-tiap titik anting-anting untuk membentuk sikel

Graf Helm Hn adalah graf yang didapatkan dari sebuah graf roda dengan menambahkan sisi anting-anting pada setiap titik di sikel

Eric W Weisstein. mendefinisikan graph gear adalah graf roda dengan tambahan sebuah titik diantara tiap-tiap pasangan dari titik-titik graf yang terhubung langsung pada sikel luar

Graf Roda Wn adalah graf yang memuat graf sikel yang setiap titik pada sikel terhubung langsung dengan titik pusat

Graf kubus (cube graph) adalah graf sederhana yang himpunan titiknya berupa himpunan tupel-n binar (binary n-tupel) (a1, a2, …, an), yaitu a1 adalah 0 atau 1, i = 1, 2, 3, …, n, dan dua titik terhubung langsung jika dan hanya jika dua tupel yang bersesuaian berbeda ditepat satu tempat. Graf kubus yang diperoleh dinyatakan dengan Qn (Purwanto, 1998:23)

Graf yang terdiri dari satu lintasan disebut graf lintasan. (Purwanto, 1998:22).
Graf lintasan dengan n titik dinotasikan dengan Pn, dengan n bilangan asli

Graf sikel adalah graf yang terdiri dari satu sikel (Purwanto, 1998:22).Graf sikel dinotasikan Cn

Graf bipartisi komplit (complete bipartite graph) adalah graf bipartisi dengan himpunan partisi X dan Y sehingga masing-masing titik di X dihubungkan dengan masing-masing titik di Y oleh tepat satu sisi. Jika |X| = m dan |Y| = n, maka graf bipartisi tersebut dinyatakan dengan Km,n. (Purwanto, 1998:22)

Graf bipartisi (bipartite graph) adalah graf yang himpunan titiknya dapat dipisahkan menjadi dua himpunan tak kosong X dan Y sehingga masing-masing sisi di graf tersebut menghubungkan satu titik di X dan satu titik di Y; X dan Y disebut himpunan partisi (Purwanto, 1998:21)

Graf komplit (Complete Graph) adalah graf dengan setiap pasang titik yang berbeda dihubungkan oleh satu sisi. Graf komplit dengan n titik dinyatakan dengan Kn (Purwanto, 1998:21)

Sebuah jalan (walk) u – v di graf G adalah barisan berhingga (tak kosong). W : u = v0, e1, v1, e2, v2, ...., en – vn = v yang berselang seling antara titik dan sisi, yang dimulai dari titik dan diakhiri dengan titik sedemikian hingga untuk 0≤ i ≤ n. Dengan ei = vi-1vi adalah sisi di G.
v0 disebut titik awal, vn disebut titik akhir, v1, v2, ..., vn-1 disebut titik interval, dan n menyatakan panjang dari W (Chartrand dan Lesniak, 1986:26)

Derajat suatu titik v pada sebuah graf G, ditulis dengan deg(v), adalah jumlah sisi yang incident pada v. Dengan kata lain, jumlah sisi yang memuat v sebagai titik ujung. Titik v dikatakan genap atau ganjil tergantung dari jumlah deg(v) genap atau ganjil (Chartrand dan Lesniak, 1986: 8)

Graf G adalah pasangan himpunan (V, E) dengan V adalah himpunan tidak kosong dan berhingga dari obyek-obyek yang disebut sebagai titik dan E adalah himpunan (mungkin kosong) pasangan tak berurutan dari titik-titik berbeda di G yang disebut sebagai sisi. Himpunan titik di G dinotasikan dengan V(G) dan himpunan sisi dinotasikan dengan E(G). Sedangkan banyaknya unsur di V disebut order dari G dan dilambangkan dengan p(G) dan banyaknya unsur di E disebut ukuran dari G dan dilambangkan dengan q(G). Jika graf yang dibicarakan hanya graf G, maka order dan ukuran dari G tersebut cukup ditulis dengan p dan q (Chartrand dan Lesniak, 1986:4).
Dari uraian di atas, maka suatu graf tidak boleh mempunyai sisi rangkap dan loop. Sisi rangkap dari suatu graf adalah jika dua titik yang dihubungkan oleh lebih dari satu sisi. Sedangkan yang disebut dengan loop adalah suatu sisi yang menghubungkan suatu titik dengan dirinya sendiri (Suryanto dalam Fitria, 2007:6). Graf yang mempunyai sisi rangkap dan loop sebut multigraf.

Dewasa ini semakin banyak muncul penggunaan model matematika maupun penalaran matematika sebagai alat bantu dalam menyelesaikan permasalahan yang dihadapi dalam berbagai disiplin ilmu. Teori graf merupakan salah satu cabang matematika yang penting dan banyak manfaatnya karena teori-teorinya dapat diterapkan untuk memecahkan masalah dalam kehidupan sehari-hari. Dengan mengkaji dan menganalisa model atau rumusan teori graf dapat diperlihatkan peranan dan kegunaannya dalam memecahkan permasalahan. Permasalahan yang dirumuskan dengan teori graf dibuat sederhana, yaitu diambil aspek-aspek yang diperlukan dan dibuang aspek-aspek lainnya
Terkait dengan pernyataan di atas, pewarnaan titik pada graf merupakan salah satu dari materi pada teori graf yang berkembang dan mendapat perhatian saat ini. Dengan mengkaji dan menganalisis suatu pewarnaan titik pada graf tertentu, akan didapat suatu perumusan yang akan lebih memudahkan proses pengaplikasiannya ke dunia nyata.

Matematika merupakan salah satu cabang ilmu yang mendasari berbagai macam ilmu yang lain dan selalu menghadapi berbagai macam fenomena yang semakin kompleks. Hal ini disebabkan oleh kemajuan ilmu pengetahuan dan teknologi, serta matematika merupakan bahasa proses, teori dan aplikasi ilmu yang memberikan suatu bentuk dan kemanfaatan. Perhitungan matematika menjadi dasar bagi desain ilmu teknik, fisika, kimia maupun disiplin ilmu yang lainnya. Para ahli dari berbagai disiplin ilmu, menggunakan matematika untuk berbagai keperluan yang berkaitan dengan keilmuan mereka. Misalnya para ahli fisika menggunakan matematika untuk mengukur kuat arus listrik, merancang pesawat ruang angkasa, menganalisis gerak, mengukur kecepatan,