For any set $X$ set $[X]^2 = \big\{\{x,y\}: x,y \in X, x\neq y\big\}$. 
Suppose $G=(V,E)$ is a simple, undirected graph, let $v^\* \notin V$. We let $a(G)$ be the minimal number of edges that we need to attach $v^\*$ to the vertices of $G$ such that the chromatic number increases, formally: $$a(G) = \min\{|Z| : Z\subseteq [V\cup \{v^\*\}]^2\land v^\* \in Z \land \chi\big((V\cup\{v^\*\}, E\cup Z)\big) = \chi(G)+1\}.$$
It's easy to see that $a(G) \geq \chi(G)$ for every graph $G$. Do we have equality? Or can $a(G)$ become arbitrarily big compared to $\chi(G)$?



Vertex-adding number
The vertex-adding number can be arbitrarily large compared to the chromatic number. To see this consider a long odd cycle, $C\_{2k+1}$. Then $\chi(C\_{2k+1})=3$, but $a(C\_{2k+1})=2k+1$. 


Note that $a(C\_{2k+1})=2k+1$ because for any proper subset $U$ of $V(C\_{2k+1})$, there is a $3$-colouring of $C\_{2k+1}$ that only uses $2$ colours on $U$. Indeed, it suffices to show this for $|U|=2k$, where we can obtain the required $3$-colouring of $C\_{2k+1}$ by using alternating colours on $U$, and a third colour for the last vertex. 


