Graph folding and chromatic number
Author
Campena, Francis Joseph
Gervacio, Severino
Full text
https://www.revistaproyecciones.cl/index.php/proyecciones/article/view/574110.22199/issn.0717-6279-5741
Abstract
Given a connected graph G, identify two vertices if they have a common neighbor and then reduce the resulting multiple edges to simple edges. Repeat the process until the result is a complete graph. This process is called folding a graph.
We show here that any connected graph G which is not complete folds onto the connected graph Kp where p = χ(G), the chromatic number of G. Furthermore, the set of all integers p such that G folds onto Kp consist of consecutive integers, the smallest of which is χ(G).
One particular result of this study is that a sharp upper bound was obtained on the largest complete graph which a graph can be folded onto.