2
$\begingroup$

What's the usual method for proving the criticality of a graph?

I've been trying out different methods and theorems but I can't find a decent method that's really convincing.

Thanks a lot in advance!

  • 1
    A graph is critical if every one of its proper subgraphs (subgraph not equal to the original) has a chromatic color less than the original.2011-02-13

1 Answers 1

1

If $G$ is $n$-critical (i.e. $\chi(G) = n$), then $\delta(G) \geq n-1$. So if $\delta(G) < n-1$ then $G$ is not $n$-critical.

  • 0
    Yuval- the 5-cycle is 3-critical (deleting any vertex gives a bipartite graph), but it is not the complete graph.2011-11-28