Open AccessColouring of graphs by HB colour matrix algorithm method
Author(s) -
A. A. Bhange,
H. R. Bhapkar
Publication year - 2021
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1743/1/012010
Subject(s) - python (programming language) , computer science , chromatic scale , vertex (graph theory) , combinatorics , algorithm , mathematics , graph , operating system
Graph Colouring is a chief element in graph theory with tremendous applicability in computer science like data mining, clustering, networking, image segmentation etc. And a variety of implementations in aircraft scheduling, register allocation, sudoku, mobile networking, etc. Various algorithms were contrived for vertex colouring. This paper defines the HB colour matrix method and its kinds. There are three types of such matrices, Vertex HB colour matrix (VHBCM), Edge HB Colour matrix (EHBCM), and Region HB colour matrix (RHBCM). Also, the HB colour matrix algorithm is developed using a special assignment method, which gives the chromatic number of the given graph. Further, the algorithm is used to develop the python program, giving time complexity O(n) and space complexity O(n 2 ). Also, the output of the python program for some standard graphs is calculated. The Similar algorithm can be developed for edge and face colouring of the graphs. Colouring of the graph further can be extended to perfect colouring.