Hidden Edges in Graph Coloring
2007
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.