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)$?
$\begingroup$ $\endgroup$
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
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.
