2
$\begingroup$

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)$?

$\endgroup$
6
$\begingroup$

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.

| cite | improve this answer | |
$\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.