Skip to main content
added 19 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

YesYes, such a graph does exist. Let $G$ be obtained from the complete graph $K_{100}$ by adding two non-adjacent vertices $v$ and $w$ such that $|N_G(v)|=|N_G(w)|=50$ and $N_G(v) \cup N_G(w)=V(K_{100})$. ThenHere, $N_G(v)$ denotes the set of vertices of $G$ which are adjacent to $v$. Then collapsing $v$ and $w$ in $G$ yields $K_{101}$, which increases the chromatic number. On the other hand, it is easy to see that adding any edge to $G$ does not increase the chromatic number.

Yes. Let $G$ be obtained from $K_{100}$ by adding two non-adjacent vertices $v$ and $w$ such that $|N_G(v)|=|N_G(w)|=50$ and $N_G(v) \cup N_G(w)=V(K_{100})$. Then collapsing $v$ and $w$ in $G$ yields $K_{101}$, which increases the chromatic number. On the other hand, it is easy to see that adding any edge to $G$ does not increase the chromatic number.

Yes, such a graph does exist. Let $G$ be obtained from the complete graph $K_{100}$ by adding two non-adjacent vertices $v$ and $w$ such that $|N_G(v)|=|N_G(w)|=50$ and $N_G(v) \cup N_G(w)=V(K_{100})$. Here, $N_G(v)$ denotes the set of vertices of $G$ which are adjacent to $v$. Then collapsing $v$ and $w$ in $G$ yields $K_{101}$, which increases the chromatic number. On the other hand, it is easy to see that adding any edge to $G$ does not increase the chromatic number.

Post Undeleted by Tony Huynh
added 52 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

No, there does not exist such a graph Yes. Let $vw$$G$ be aobtained from $K_{100}$ by adding two non-edge ofadjacent vertices $G$ such that collapsing$v$ and $vw$ increases the chromatic number. This means$w$ such that for every $\chi(G)$-colouring of$|N_G(v)|=|N_G(w)|=50$ and $G$,$N_G(v) \cup N_G(w)=V(K_{100})$. Then collapsing $v$ and $w$ must be coloured differently. Equivalently,in $\chi(G + uv)=\chi(G)+1$, so condition$G$ yields (2)$K_{101}$, which increases the chromatic number. On the other hand, it is easy to see that adding any edge to $G$ does not satisfiedincrease the chromatic number.

No, there does not exist such a graph. Let $vw$ be a non-edge of $G$ such that collapsing $vw$ increases the chromatic number. This means that for every $\chi(G)$-colouring of $G$, $v$ and $w$ must be coloured differently. Equivalently, $\chi(G + uv)=\chi(G)+1$, so condition (2) is not satisfied.

Yes. Let $G$ be obtained from $K_{100}$ by adding two non-adjacent vertices $v$ and $w$ such that $|N_G(v)|=|N_G(w)|=50$ and $N_G(v) \cup N_G(w)=V(K_{100})$. Then collapsing $v$ and $w$ in $G$ yields $K_{101}$, which increases the chromatic number. On the other hand, it is easy to see that adding any edge to $G$ does not increase the chromatic number.

Post Deleted by Tony Huynh
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

No, there does not exist such a graph. Let $vw$ be a non-edge of $G$ such that collapsing $vw$ increases the chromatic number. This means that for every $\chi(G)$-colouring of $G$, $v$ and $w$ must be coloured differently. Equivalently, $\chi(G + uv)=\chi(G)+1$, so condition (2) is not satisfied.