# 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):

1. 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$.
2. 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 do not quite understand step 1, do you mean that you delete either $v_1$ or $v_2$ and all incident edges from $G$? – lattice Jun 15 '16 at 17:27
• @lattice Nope. I mean "identifying"(=gluing) two vertices, not deleting any of them. – Henry Jun 16 '16 at 0:40
• Oh okay, now I got it. Nice question, and I agree with Mosquite's second answer. – lattice Jun 16 '16 at 5:30

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$.

• Nice example. Thanks. – Henry Jun 16 '16 at 7:22

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.

• It seems that not ALL pair of nonadjacent vertices of the Grötzsch graph will result in a graph that has no triangles... Can you specify a pair? I cannot find one easily. – Henry Jun 15 '16 at 11:04
• The Grötzsch graph itself already has no triangles, so applying (1) (possibly multiple times) will always result in a graph with no triangles, since (if I got (1) correctly) you are only removing vertices and edges. Also, any nonadjacent vertices are connected via a path of length 2, which yields a subgraph that is $K_3$ minus an edge, so it is possible to apply (1) at least once. Since the Grötzsch graph is the smallest graph with no triangles and chromatic number $4$, applying (1) once will give a graph with a smaller chromatic number. Thus, HDFF does not lead to $K_{\chi(G)}$ in this case. – lattice Jun 15 '16 at 17:39
• Oops, on closer inspection I see that there is a triangle in the resulting graph. My bad. – Mosquite Jun 15 '16 at 21:14