Return to Revisions

Let $H$ be a graph with $\omega(G)=2$ and $\chi(G)=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$.