3
$\begingroup$

Let $G=(V,E)$ be a finite simple, undirected graph. Given $f:V\to \mathbb{Z}$ we define the neighborhood sum function $\mathrm{nsum}_f:V\to\mathbb{Z}$ by setting

$\mathrm{nsum}_f(v) = \sum\{f(w):w\in N(v)\}$ for all $v\in V$.

We say that a graph $G=(V,E)$ is sum-balanceable if there is an injective function $f:V\to\mathbb{Z}$ such that $\mathrm{nsum}_f(v) = 0$ for all $v\in V$.

Is there for every positive integer $n\in\mathbb{N}$ a sum-balanceable graph $G$ with $\chi(G) =n$?

$\endgroup$

1 Answer 1

3
$\begingroup$

Consider the graph with vertices $\{x,y\}\times\{ 1,2,...n\}$, and every two vertices connected unless they are of the form $(x,a),(y,a)$ $(a\in\{1,2,...n\})$.

The graph have chromatic number $n$, since the graph is perfect and its clique number is $n$.

Noticing that the vertex $(x,a)$ is connected to $(x,k)$ and $(y,k)$ for $k\neq a$, the graph is sum-balanceable since we can assign $k$ to vertex $(x,k)$ and $-k$ to vertex $(y,k)$ for $k$ in $\{1,2,...n\}$. In fact, any $f$ satisfying $ ∀k:f((x,k))=-f((y,k))$ would work.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.