$\chi(G)$ ( vertex-chromatic number of a graph like $G$) is the minimum number of colors which is enough to color every vertex of $G$ such that no two adjacent vertices have the same color.

A graph like G is called k-vertex-critical if $\chi(G)=k$ and for each $v \in V(G)\space\space\space\space\chi(G-v) \lt \chi(G)$ .

$\chi'(G)$ ( edge-chromatic number of a graph like $G$) is the minimum number of colors which is enough to color every edge of $G$ such that no two edges of the same color share a common vertex.

A graph like G is called k-edge-critical if $\chi'(G)=k$ and for each $e \in E(G)\space\space\space\space\chi'(G-e) \lt \chi'(G)$ .

Now the question :
Can you find a vertex-critical graph which is not edge-critical?

Note: I don't want a graph with critical vertices and without critical edges. This question is different. Here, we deal with every edge and every vertex not just one.

Thanks in advance.


$K_4$ would be an example.

A proper vertex-coloring requires 4 colors, and $K_4-v=K_3$ requires only 3 colors, so $K_4$ is vertex critical.

A proper edge-coloring requires 3 colors (verify!), but $K_4-e$ still has a triangle, so $K_4-e$ still requires 3 colors, so $K_4$ is not edge-critical.

EDIT: $K_{2n}$ is an example for any $n\geq2$. It is obviously vertex-critical. A proper edge-coloring requires $2n-1$ colors (verify!), but $K_{2n}-e$ still requires $2n-1$ colors, since it has maximum degree $2n-1$, so $K_{2n}$ is not edge-critical.

  • $\begingroup$ It seems that your answer is correct ... but i want a more complicated example... $\endgroup$ – Arman Malekzadeh May 13 '16 at 14:37
  • $\begingroup$ @ArmanMalekzade: please define "complicated". $\endgroup$ – Leen Droogendijk May 14 '16 at 9:23
  • $\begingroup$ our teacher told us that this graph has 8 or 9 vertices $\endgroup$ – Arman Malekzadeh May 14 '16 at 11:38
  • $\begingroup$ @ArmanMalekzade: see edit, you now have an infinite number of examples, one of them has 8 vertices. $\endgroup$ – Leen Droogendijk May 14 '16 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.