Topology and Graph in Graph Coloring

Introduction

The aim of this study is studying coloring graph by colorable functions and explicating the conditions and their performance on known graphs. Fixing barriers of using the method such as the conditions of creating a function, defining the type of functions, etc. are among the main purposes of the study. To this end, at first, colorability of graphs is defined and then its elements are analyzed.

Definition: Let f : X → X be a graph without fixed point. f is colorable with k colors, if there is , where all C_i s do not include {f(x, x)}. Or similarly, for every , there is the equation ∅ = C_i ∩ f(C_i).

Then, to determine the chromatic number of graphs by these functions, all various theorems and lemmas are stated. It is shown that every graph is colored with a specific number by one of the colored functions

Material and methods

At first, coloring function is defined and its performance is stated. When the colored theorem is stated, which is the main element in coloring functions, the performance of the functions in coloring a graph is explored. Finally, the chromatic number of every graph by the functions is determined through some theorems and lemmas.

Results and discussion

In this study the chromatic number of some graphs such as simple graph, triangular graph, complete graph, etc. was determined by these functions. It was shown that the performance of the functions are complicated at first, but they have a good performance and simplicity in every point.

Conclusion

The study concluded that:

- Except when you cannot define a function for a graph at all, the chromatic number of every graph is determinable in this way,

- The efficiency of this method in finding the chromatic number of graphs of many vertices is much easier.

- Users’ probability of mistake in estimating the chromatic number of graphs of many vertices is very low../files/site1/files/71/13.pdf