ABSTRACT
In this work, the concept of implicit edges is applied to the problem of graph vertex colorability, presenting some interesting results.
Graph Vertex Coloring is the task to assign a color to every vertex of a graph in such a way that no two adjacent vertices are assigned the same color, and the chromatic number of a graph, is the minimum number of distinct colors needed to properly color a graph. The importance of graph coloring resides in its general applicability as a process of partitioning a collection of
objects into disjoint sets fulfilling a set of constraints between that objects. For a good reference on graph coloring problems the reader can review the excellent book of Jensen and Toft [3]. We are presenting a theory about the implication structure in graph coloring guided by the concept of implicit edge. We think that the study of this kind of relations has a high applicability in a wide range of experimental and theoretical fields of research. This study can help to unveil a wide range of "hidden" phenomena in a wide range of scientific disciplines like physics, chemistry, and of course, discrete mathematics and computer science.
