Graph folding and chromatic number
Francis Joseph H. Campeña, Severino V. Gervacio · Proyecciones (Antofagasta) · 2023
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.