0
$\begingroup$

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

$\endgroup$

1 Answer 1

2
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .