{'fraction_non_alphanumeric': 0.024760734041619107, 'fraction_numerical': 0.007990165949600492, 'mean_word_length': 4.352443609022556, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Region Coloring in Minahasa Regency Using Sequential Color Algorithm

Received : 20 June 2019 Received in revised form : 23 July 2019 Available online : 25 July 2019


INTRODUCTION
Graph theory is a very interesting subject to be explored because it has a variety of models whose application is very broad on solving problems of human life today. Although graph theory is part of exact sciences, i.e. mathematics, which in ordinary societies is only known by general formulas for solving real mathematical problems, in actual application models of graph theory can be associated with other fields of science such as communication networks, chemistry, biology, computer sciences, transportation, operations research, and so on.
Graph theory has existed since 1736 through Euler's book about problem-solving efforts on the Konigsberg bridge which was one of the famous bridges in Europe at that time. In daily life, the graph is useful for describing various structures that represent several objects so they are easy to understand. For example, on a map, cities are represented as vertices and roads that connect the cities are represented as edges.
One of the graph theory's models that can be applied in daily life is map coloring. The graph here is represented as a map. The coloring is done in 3 ways that are by coloring the vertices, coloring the edges, then coloring the regions. The aim is to find out the least number of colors from a map called chromatic numbers.
Nowadays, there are so many algorithms that can be used for graph coloring. The sequential color algorithm is one of them. The regional coloring of a graph in its application is to color the area on the map, provided that no area of the same color is neighboring. The colors used also can be minimized by this algorithm.
The coloring of the map that uses minimum colors will facilitate coloring the map with a very large area. The map does not have to be colored with the same number of colors as the number of areas that will be colored but only by using the minimum color, the areas on the map can be sorted between one area and another.
The sequential color algorithm is to coloring a graph with color, which is a positive integer. The Graph Theory is one of the mathematical sciences whose application is very wide in human life. One of theory graph applications is Map Coloring. This research discusses how to color the map of Minahasa Regency by using the possible minimum color. The algorithm used to determine the minimum color in coloring the region of Minahasa Regency is Sequential Color Algorithm. The Sequential Color Algorithm is an algorithm used in coloring a graph with k-color, where k is a possitive integer. Based on the results of this research, the Sequential Color Agorithm can be used to color the map of Minahasa Regency with the minimum number of colors or chromatic number χ(G) obtained in the coloring of 25 sub-districts on the map of Minahasa Regency are 3 colors (χ(G) = 3). method used is coloring graph directly with minimum colors [1].
Referring to the previous research [2] that applied on the map in Kuantan Singingi Regency, coloring on maps can be modeled using graph theory. The use of graph theory is specialized in map coloring and the number of colors that used to color the area on the map. Objects represented as dots or vertices, while the regional boundaries represented as lines or edges. The solution is done by vertices coloring method using the Sequential Color Algorithm. Based on the background described above, the author wants to do a map coloring research using Sequential Color Algorithm, so the title that the author appoints is "Region Coloring in Minahasa Regency using The Sequential Color Algorithm".

History of Graph Theory
The origin of graph theory started with the problem of Konigsberg bridge, in 1735. This problem lead to the concept of Eulerian Graph. Euler studied the problem of Konigsberg bridge and constructed a structure to solve the problem called Eulerian graph [3].
A graph is used to represent discrete objects and relationships between these objects. The visual representation of a graph is to declare an object expressed with a dot, circle, or point, while the relationship between objects is expressed as a line or edges [4].

Graph Definition
A Graph G=(V,E) consists of a V, a set of vertices that are not empty and E, a set of edges. Each edge has between one or two points connected to it, called and points [5].
Two vertices on non-directed graph G is said to be neighbors if the two are connected directly to a side. In other words, u adjacent to v if (u,v) is an edge in a graph degree of a node in non-trending graph is the number of side by side with that node [6].

Varieties of Graph
Graphs can be grouped into several categories (types) depending on the viewpoint of the grouping. Graph grouping can be seen based on the presence or absence of double sides or side edges or based on direction orientation on the side [4]. 1. Simple graph and Unsimple graph 2. Directed graph and Undirected graph Basic Terminology 1.
Adjacent and Incident Two vertices v and w are said to be Adjacent when both are connected directly to an e=(v,w), and side e=(v.w) is said to be incident or directly related to vertices v and w [7].

Degree
The degree of a vertex v of G is the number of edges incident with v, and is written deg(v); in calculating the degree of v, usually make the convention that a loop at v contributes 2 (rather than 1) to the degree of v [7]. 3.
Connected and Disconnected Graph Suppose that G is a graph, then every two vertices v and w in G said to be connected in and only if there is a path from vertex v to w or w to v. Graph G is said to be disconnected if and only if there are two vertices in G which are disconnected [8].

Planar Graph
According to Wilson [7] planar graph is a graph that can be drawn in the plane without crossings, so that is no two edges intersect geometrically except at a vertex to which both are incident. Any such drawing is a plane drawing. For convenience, we often use the abbreviation plane graph for a plane drawing of a planar graph. For example, figure 1 shows two drawing of the planar graph K4.

Dual Graph
Dual graph is a planar graph G which is represented as a plane graph, so a graph of G* can be made which is geometrically is dual from planar graph in the following way [9]. 1. Every area or face in G, make a vertex which is a vertex for G*. 2. Every edge e in G, draw the edge e* (which is the edge of G*) that intersect the edge of e. The edge e* connects two vertices v1* and is separated by the edge e in G.

Graph Coloring
In graph theory, graph coloring is a form of graph labeling, that is by giving color to graph elements which will be subject to understanding problem constraints. There are three types of graph coloring problems that is vertex coloring, edge coloring, and region coloring [10].

Map Coloring
Some principles must be considered in coloring maps that are [11]: 1. The number of colors that used must be as minimum as possible. 2. Coloring the areas on the map means coloring the vertices in the graph. 3. Two vertices that connected by one or more edges cannot be given the same color. 4. In coloring the map, use an optimum color, meaning the new color will be used if the first color cannot be used again.

Sequential Color Algorithm
The sequential color algorithm is an algorithm for coloring a graph with -color, where is a positive integer. The method that used by this algorithm is by directly coloring a graph with as little color as possible [1]. The followings are the steps of the sequential color algorithm: has become the color of that adjacent with . is set of colors that might be a color from . 4. Each vertex has been colored and the number of colors used is calculated.

Time and Research Place
This research has been done at Advanced Computer Laboratory Department of Mathematics, Faculty of Mathematics and Natural Sciences, Sam Ratulangi University from December 2018 until May 2019.

Research Methods
The method that used in this research is a literature study by studying the literature related to the graph and its coloring and the sequential color algorithm.

Research Steps
The steps to be used in completing this research are as follows:

Dual Graph of Minahasa Regency's Map
Dual graphs from the map of Minahasa regency are made by representing existing sub-districts as vertices and neighboring vertices connected by edges.

Figure 5. Dual graph from the Minahasa
Regency's map

Region Coloring of Minahasa Regency's Map uses The Sequential Color Algorithm
Region coloring on the Minahasa regency's map is done by using the concept of region coloring, which is to color each region that neighboring with a different color. The following will explain how the sequential color algorithm works for coloring the Minahasa regency map.
Step 1: Determine the set of vertices and edges in the graph. Graph = ( , ) is a graph consisting of set vertices and edges. if the vertex on the graph has not been named, then the graph must be named first, for example by the name 1 , 2 , 3 , … , . then suppose the colors that might color the vertices are 1,2,3, … , .

Determine The Minimum Number of colors of Minahasa Regency Map
The minimum number of colors or called chromatic numbers χ( ) obtained from the results of coloring the sub-district of the Minahasa regency map using the sequential color algorithm can be seen from the number of colors that needed in the graph coloring. According to the concept of region coloring, vertices on dual graphs of graphs that representing maps of Minahasa regency represent existing sub-districts, so that the colors used for a vertex mean colors that can be used for coloring the region they represent.
Based on the results obtained from the vertex coloring of the dual map of the Minahasa regency map using a sequential color algorithm, the minimum color obtained is 3 colors. So the colors needed to color the 25 sub-districts in Minahasa regency only need 3 colors (χ( ) = 3) in the coloring process. As you can see that the color that becomes the color of the existing sub-district is the node color in the previous dual graph, because it is in accordance with the concept of regional coloring, each color that becomes the color of the sub-district on the map is represented by the color of the vertices on the second part representing each sub-district.

Conclusions
Based on the results obtained, it can be concluded that:

1.
Region Coloring in the map of Minahasa Regency can be done using The Sequential Color Algorithm by creating a dual graph form of the Minahasa Regency's Map.

2.
The Minimum number of colors or chromatic numbers χ(G) obtained in the coloring of 25 subdistricts on the map of Minahasa Regency in this research obtained 3 colors (χ(G) = 3), with colors between neighboring regions having different color.

Suggestions
This final project discusses one of the application in the field of graph theory about graph coloring which is applied to the coloring of regions on the map using Sequential Color Algorithm. Another research that can be developed from this study is that graph theory coloring can also be done on wider maps with different algorithms and using mathematical software or applied in another cases that has been explained in Chapter before.