Vertex colouring using the adjacency matrix

Abstract

Recently, graph theory is one of the most rapidly developing sciences. Graphs in its applications are generally used to represent discrete objects and relationships between these objects. The visual representation of a graph is to declare an object as a vertex, while the relationship between objects is expressed as an edge. One topic in graph theory is colouring. This graph colouring is divided into vertex colouring, edge colouring and area colouring. The problem of the vertex colouring is to determine the minimum number of colours to colour the vertex so that the interconnected vertex has different colours. The problem of edge colouring is to determine the minimum number of colours to colour the edge so that the interconnected edge has different colours. The problem with area colouring is to determine the minimum number of colours to colour the area so that the adjacent area has a different colour. In this article the discussion will focus on the problem of vertex colouring. Previously there have been several vertex colouring methods, such as the Welch Powell method and the backtracking method. In this paper we will discuss the method of vertex colouring using the adjacent matrix. Adjacent matrix (𝑀) is a square matrix where the element 𝑀𝑖𝑗 is 1 if 𝑉𝑖𝑉𝑗 is connected and element 𝑀𝑖𝑗 is 0 if 𝑉𝑖𝑉𝑗 is not connected. In the discussion, this method is presented in the form of the pseducode and flowchart so that it can be computerized more easily. The novelty of this research is to detect the character of the adjacency matrix so that it can apply to vertex colouring through the matrix.