Reasons for which a graph may be not $k$ colorable? While reasoning a bit on this question, I've tried to identify all the different reasons for which a graph $G = (V_G,E_G)$ may fail to be $k$ colorable. These are the only 2 reasons that I was able to identify so far:


$G$ contains a clique of size $k+1$. This is the obvious reason.
There exists a subgraph $H = (V_H, E_H)$ of $G$ such that both the following statements are true:


$H$ is not $k-1$ colorable.
$\exists x \in V_G - V_H\ \forall y \in V_H\ \{x,y\} \in E_G$. In other words there exists a node $x$ in $G$ but not in $H$, such that $x$ is connected to each node in $H$.



We can see the 2 reasons above as rules. By recursively applying them, the only 2 ways to build a non $k$ colorable graph which does not contain a $k+1$ clique are:


Start from a cycle of even length (which is $2$ colorable), then apply rule 2 for $k-1$ times. Note that an edge is not considered to be a cycle of length $2$ (otherwise this process would have the effect of building a $k+1$ clique).
Start from a cycle of odd length (which is $3$ colorable), then apply rule 2 for $k-2$ times. The length of the starting cycle must be greater than $3$ (otherwise this process would have the effect of building a $k+1$ clique).



  Question  
  
  Is there any further reason, other than those 2 above, that makes a graph non $k$ colorable?


$\ $
Update 30/11/2012    

More precisely, what I need is some theorem of the form:


  A graph $G$ has chromatic number $\chi(G) = k + 1$ if and only if...


Hajós calculus, pointed out by Yuval Filmus in his answer, is a perfect example of what I am looking for, as a graph $G$ has chromatic number $\chi(G) = k + 1$ if and only if it can be derived from axiom $K_{k+1}$ by repeatedly applying the 2 rules of inference of the calculus. The Hajós number $h(G)$ is then the minimum number of steps necessary to derive $G$ (i.e. it is the length of the shortest proof).

It is very interesting that:


The question of whether there exists a graph $G$ whose $h(G)$ is exponential in the size of $G$ is still open.
If such $G$ does not exist, then $NP = coNP$.
You should check the Hajós calculus. Hajós showed that every graph with chromatic number at least $k$ has a subgraph which has a "reason" for requiring $k$ colors. The reason in question is a proof system for requiring $k$ colors. The only axiom is $K_k$, and there are two rules of inference. See also this paper by Pitassi and Urquhart on the efficiency of this proof system.