BILANGAN KROMATIK LINIER DARI KOMPLEKS PERSEKITARAN GRAF SEDERHANA

Abstract

Pewarnaan k- linier dari komplek simplisial adalah pewarnaan α: X → [k]

dari  Δ  jika  dan hanya  jika  α(x)  =  α(y)  untuk suatu  x,y ∈  X  maka  Ƒ∆(   ) ⊆  Ƒ∆(   )

atau  Ƒ∆(   )  ⊆  Ƒ∆(   )  berlaku.  Bilangan  kromatik  linier  dari  komplek  simplisial

adalah  bilangan  bulat  positif  k  terakhir  dari  pewarnaan  k-linier  pada  komplek

simplisial.   Pewarnaan   k-   linier   dan   bilangan   kromatik   linier   dari   komplek

simplisial  dapat dikembangkan pada komplek persekitaran graf.

Permasalahan   yang   diangkat   dalam   skripsi   ini   adalah   bagaimana   cara

mencari  bilangan  kromatik  linier pada  komplek  persekitaran  graf  sederhana  dan

bagaimana   hubungan   antara   bilangan   kromatik   pada   graf   sederhana   dengan

bilangan kromatik linier pada komplek persekitaran graf sederhana.  Cara mencari

bilangan kromatik linier dari komplek persekitaran graf sederhana adalah mencari

bilangan    bulat    positif    terakhir    k    dari    pewarnaan   k-linier    pada    komplek

persekitaran.

Untuk sebarang graf G, λ(N(G)) ≥   X(G) dimana  X(G) dinotasikan dengan

bilangan kromatik titik pada graf  G;  Misal G  adalah  graf,  maka X  (G) =  maks{ X

(Gi)    Gi  adalah komponen dari G}; Misalkan G adalah graf dengan G1,  G2,…,Gn.

maka  λ(N (G))  = ∑     (N (     ));  Jika  G adalah  graph  N-linier, maka  G terhubung;

Jika  G  isomorfik  dengan  H,  maka  λ  (N  (G))  =  λ  (N  (H));  Jika  G  adalah  graf  N-

linier dan G ≅ H, maka H adalah graf N-linier.

Kata       kunci:       komplek   simplisial,    graf    sederhana,   komplek    persekitaran,

pewarnaan linier, bilangan kromatik