Reducing a graph without lowering its chromatic number While trying to find an algorithm to reduce a graph without lowering its chromatic number, I made the following algorithm (but not sure if it works): 


*

*Given a (simple) graph $G$, look for subgraphs of $m$ ($m \geq 2$) vertices, which are isomorphic to $K_m$ minus an edge, and whose unfilled edge (say, $e=(v_1,v_2)$) is still unfilled in $G$, i.e. $e\not\in E(G)$. Pick such a subgraph with maximal $m$, and then identify $v_1$ and $v_2$. After reducing some multiple edges to simple edges, we get a new simple graph $G'$ whose number of vertices is one less than that of $G$. 

*Repeat #1 until there is no such subgraph. 


Let's call this algorithm "Highest dimension first folding (HDFF)". I wonder if HDFF always gives us $K_{\chi(G)}$, where $\chi(G)$ is the chromatic number of $G$, and $K_n$ is the complete graph on $n$ vertices. 

I figured it out. Your algorithm doesn't preserve the chromatic number (it cannot lower the chromatic number however) and this time I've found a correct reason.
Consider the graph,
$G$.
The vertices $v_1, v_2, x_1, x_2$ of $G$ create a $K_4$ with the edge between $v_1$ and $v_2$ missing. The largest $K_m - e$ in this graph has $m=3$ and one is given by $x_1, x_2, v_1, v_2$.
Applying (1) to this graph with $v_1$ and $v_2$ identified produces a graph with an induced $K_5$ subgraph. Therefore it has chromatic number at least 5. However, $G$ has chromatic number 4 as we can see from the coloring in the figure of $G$.
