PEWARNAAN-SISI PADA GRAF KOMPLET YANG MEMUAT SIKEL 𝑪𝟒-TERWARNA SEJATI

EDGE-COLORING COMPELTE GRAPH WHICH CONTAIN PROPERLY COLORED 𝑪𝟒

Misalkan  graf dan  subgraf dari . Semua sisi graf  diberi sembarang warna sedemikian hingga terhadap pewarnaan tersebut terdapat subgaf  terwarna sejati. Namun, permasalahan ini sulit dibuktikan, sehingga diberi batasan masalah. Misalkan  graf komplet dengan  titik dengan  minimum 4 dan  subgraf dari  adalah sikel dengan 4 titik. Semua sisi graf komplet  diberi sembarang warna sedemikian hingga terhadap pewarnaan tersebut terdapat subgraf berupa sikel H terwarna sejati. Dengan penelitian ini telah dibuktikan bahwa terdapat syarat cukup di mana graf  memuat subgraf  yang merupakan sikel  terwarna sejati melalui derajat warna minimum. Dalam penelitian ini telah dibuktikan juga bahwa terdapat syarat cukup di mana graf  memuat subgraf  yang merupakan sikel  terwarna sejati melalui kardinalitas dari gabungan warna tetangga titik  dan warna tetangga titik .

Kata kunci: Pewarnaan sisi, graf komplet, graf sikel , serta derajat warna minimum.

Suppose  is a graph and  is a subgraph of . All edges of graph  are given arbitrary colors such that there is a properly colored subgaph . However, this problem is difficult to prove, thus the problem is given a constraint. Suppose  is a complete graph with  vertices with 4 as the minimum for , and  (subgraph of ) is a cycle with 4 vertices. All edges of complete graph G are given arbitrary colors such that there is a properly colored subgraph cycle . This study has proven that there is a sufficient condition that graph  contains a properly colored  cycle through the minimum color degree. This study has also proven that there is a sufficient condition that graph  contains a properly colored  cycle through the cardinality of the union of the neighboring color of vertex  and neighboring color of vertex .

Keywords: Graph coloring, complete graph,  cycle graph, as well as minimum color degree.