Polinomial Kromatik Graf Tripartit Lengkap

Abstract

Let G=(V,E) be a connected graph and c be a proper vertex coloring using t colors. Vertex coloring on the graph G is a function c:V(G)→{1,2,…,t}, such that c(u)≠c(v) if u and v are two vertices that adjacent to each other. If a graph can be colored with t colors, then the smallest number used on the graph G is referred as a chromatic number, denoted by χ(G). While, the number of distinct ways to color the vertices of G with t colors is called as chromatic polynomial, denoted by P_G (t). In this paper, through axiomatic deductive and pattern detection methods, we propose the chromatic polynomials of complete tripartite graph, denoted by K_((l,m,n) ) for l,m ∈{1,2} and l≤m≤n.

Keywords: Chromatic Number, Chromatic Polynomial, Complete Tripartite Graph, Vertex Coloring. 

Abstrak

Misalkan G=(V,E) adalah graf terhubung dan c adalah pewarnaan titik dengan t warna. Pewarnaan titik pada graf G adalah fungsi c:V(G)→{1,2,…,t}, sedemikian sehingga c(u)≠c(v) jika u dan v merupakan dua titik yang bertetangga. Apabila suatu graf dapat diwarnai sejumlah t warna, maka paling sedikit warna yang digunakan pada graf G disebut sebagai bilangan kromatik dan dinotasikan dengan χ(G). Sedangkan, banyaknya cara yang dapat digunakan untuk mewarnai titik pada graf G dengan t warna yang disediakan disebut sebagai polinomial kromatik dan dinotasikan dengan PG(t). Pada artikel ini, dengan metode pendeteksian pola dan deduktif aksiomatik dirumuskan polinomial kromatik dari graf tripartit lengkap, yang dinotasikan dengan Kk,l,m dengan l,m ∈ {1,2} dan l≤m≤n.