تقابل توپولوژی با گراف در رنگ‌آمیزی

در این پژوهش به تعریف رنگ آمیزی گراف ها و نگاشت های رنگی می‌پردازیم و با تشریح ارکان تعریف رنگ پذیری نگاشت ها به توضیح شرایط برقراری آنها برای استفاده در زمینۀ رنگ آمیزی گراف ها می پردازیم و با بیان قضایا و لم های متعدد، نحوۀ عملکرد آنها روی گراف ها را نشان می دهیم. هم‌چنین با بیان تعریف چند نوع گراف و عدد رنگی منسوب به آنها، عدد رنگی مربوط به هر گراف به‌وسیلۀ این نگاشت ها تبیین و اثبات می کنیم. در ادامه نشان می‌داهیم عدد رنگی n+3 برای نگاشت های رنگ پذیر انطباق زیادی با عدد رنگی گراف ها دارد. هم‌چنین به این سوال پاسخ داده می شود، که آیا این نگاشت ها توانایی کافی برای رنگ آمیزی هر نوع گراف را دارند؟

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 rarr; 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 empty; = Ci cap; 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 functionsMaterial and methodsAt 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 discussionIn 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.ConclusionThe 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 rsquo; probability of mistake in estimating the chromatic number of graphs of many vertices is very low../files/site1/files/71/13.pdf