EDGE-COLORING COMPELTE GRAPH WHICH CONTAIN PROPERLY COLORED C4

Abstract

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.