Skip to main content
MathOverflow

Return to Answer

Fixed typo
Source Link
Daniel Weber
Daniel Weber
  • 3.3k
  • 1
  • 12
  • 26

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

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

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

Source Link
bof
bof
  • 13.4k
  • 2
  • 43
  • 66

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