# Clique and chromatic number when removing an edge

For any set $$X$$, let $$[X]^2=\big\{\{x,y\}: x\neq y\in X\big\}$$. If $$G=(V,E)$$ is a simple undirected graph and $$e\in E$$, let $$G\setminus e = \big(V\setminus e, E \cap [V\setminus e]^2\big)$$.

If $$G=(V,E)$$ is a finite graph, let $$\omega(G)$$ be the size of the largest clique in $$G$$ and let $$\chi(G)$$ be the chromatic number.

Question. Is there a finite graph $$G=(V,E)$$ and $$e\in E$$ such that $$\chi(G\setminus e)= \chi(G)-2$$ and $$\omega(G\setminus e) = \omega(G)$$?

• If the "double-critical graph conjecture" openproblemgarden.org/op/double_critical_graph_conjecture is correct, the answer to the question is no. Commented Jul 4 at 6:49
• @LouisEsperetHow does that follow? The OP's graph doesn't have to be double-critical, does it? There need only be one pair of adjacent vertices whose removal lowers the chromatic number by $2$.
– bof
Commented Jul 4 at 9:33

Let $$H$$ be a graph with $$\omega(H)=2$$ and $$\chi(H)=4$$, say the Grötzsch graph. Let $$G$$ be the graph obtained by taking the disjoint union $$H\cup K_2\cup K_4$$ and adding edges joining both vertices in $$K_2$$ to all vertices in $$H$$. Then $$\omega(G)=4$$ and $$\chi(G)=6$$. If $$e$$ is the edge joining the two vertices in $$K_2$$, then $$G\setminus e=H\cup K_4$$ and $$\omega(G\setminus e)=\chi(G\setminus e)=4$$.
• Can this be modified to have $G$ connected, or even $G \setminus e$? Commented Jul 4 at 11:21
• @Daniel Weber by adding one vertex, joined by a path of length 2 with one vertex in $H$, one vertex in $K_2$, one vertex in $K_4$? Commented Jul 4 at 11:54
• @DanielWeber Identify one of the vertices in $K_4$ with one of the vertices in$H$.