0
$\begingroup$

A vertex or an edge is a critical element of a graph G if its deletion would decrease the chromatic number of G. Obviously such decrement can be no more than 1 in a graph. A critical graph is a graph in which every vertex or edge is a critical element. A k-critical graph is a critical graph with chromatic number k; a graph G with chromatic number k is k-vertex-critical if each of its vertices is a critical element

My question is how to find a graph with critical vertices and without critical edges?

$\endgroup$
  • $\begingroup$ Do you want to know how to find such graphs in general, or just an example of such a graph? $\endgroup$ – Perry Elliott-Iverson May 29 '15 at 12:38
3
$\begingroup$

Maybe the easiest example of a graph with critical vertices and no critical edges is a star graph $G=(V, E)$ where $V=\{c, v_1, v_2, v_3, ..., v_{k}\}$ and $E=\{(c, v_1), (c, v_2), (c, v_3),...,(c,v_k)\}$. Note that the chromatic number is $2$, but if vertex $c$ is deleted then the chromatic number is $1$. However, if any edge is deleted then the chromatic number is still $2$.

$\endgroup$
1
$\begingroup$

A complete $k$-partite graph such that one of the partite sets has only one vertex, and each other partite set has at least 2 vertices will work. Deleting any edge will not decrease the chromatic number, but deleting the vertex in its own partite set will decrease the chromatic number.

$\endgroup$

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.