Volume 7, Issue 1 (Vol.7, No. 1, 2021)
mmr 2021, 7(1): 133-138 |
Back to browse issues page
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Topology and Graph in Graph Coloring. mmr 2021; 7 (1) :133-138
URL: http://mmr.khu.ac.ir/article-1-2749-en.html
URL: http://mmr.khu.ac.ir/article-1-2749-en.html
Abstract: (1680 Views)
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 Ci s do not include {f(x, x)}. Or similarly, for every 
, there is the equation ∅ = Ci ∩ f(Ci).
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
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 Ci s do not include {f(x, x)}. Or similarly, for every , there is the equation ∅ = Ci ∩ f(Ci).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
Type of Study: Research Paper |
Subject:
alg
Received: 2018/02/24 | Revised: 2021/05/24 | Accepted: 2019/09/25 | Published: 2021/05/31 | ePublished: 2021/05/31
Received: 2018/02/24 | Revised: 2021/05/24 | Accepted: 2019/09/25 | Published: 2021/05/31 | ePublished: 2021/05/31
| Rights and permissions | |
 |
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. |
