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. 
 A: 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$.
A: Your algorithm will result in a complete graph, but I think it doesn't preserve the chromatic number. The Grötzsch graph, is the smallest graph with no triangles and chromatic number 4. The largest induced subgraph of the Grötzsch graph that is $K_m$ minus an edge has $m=3$. Applying (1) from your algorithm to any pair of nonadjacent vertices of the Grötzsch graph will result in a graph that has no triangles and is smaller than the the Grötzsch graph and thus has a different chromatic number.
EDIT: This is wrong. There are triangles in the resulting graph after applying (1). I'll look into this a little more later.
