A Study to Find the Continuous Edge Chromatic Number and Coloring Algorithm for Graphs P

Abstract

It is well known that the matter of Graph colouring using the least number of colours is considered a complex Problem from the NP class, and it is summarized in how to colour the vertices of a Graph using the least number of colours, where no two adjacent vertices are assigned the same colour, or how the edges of a graph are coloured using the least number of colours where no two adjacent edges are assigned the same colour.

 the matter of obtaining continuous Edge colouring emerged because colouring edges does not always present the proper colouring that represents

the solution to a certain problem. this matter was taken from an open matter that was not previously worked on [1].

Since the Continuous Edge Chromatic matter is an open matter, and to pursue the academic research in this field, we presented in this research paper a new study that includes the study of colouring for Graphs P .

First, we produced graphs P  using the Cartesian product of  the two paths   and , then, we studied colouring these Graphs starting with the continuous Edge colouring.

Our study covers three cases according to the order of the Graphs  and .

Each case involves setting the algorithm of optimal continuous Edge colouring and finding the general formula of continuous Edge chromatic number precisely and viewing some explanatory examples as well as proving the possibility of applying the continuous Edge colouring to Graphs P .

Then, we concluded findings, through which, we can classify these graphs in terms of its probability to continuous Edge colouring directly, let alone find the general formula of continuous Edge chromatic number for Graphs P  in general according to its order nm.

Then we moved to study colouring the edges where we concluded the chromatic number needed to colour the edges, as well as colouring the vertices as we suggested colouring algorithm and we managed to find the required the chromatic number needed to colour the vertices, and we concluded the research with some explanatory examples. In this case we had a comprehensive study that includes the application of all types of colouring on graphs P .