3
$\begingroup$

Suppose that for any bipartite planar graph $G=(V,E)$, we can find a vertex labeling $c:V\to \{1,2,3\}$ such that for any two adjacent vertices $u$ and $w$: $$c(u)-\sum_{v\in N(u)}c(v)\neq c(w)-\sum_{v\in N(w)}c(v)$$ where $N(v)$ denotes the neighborhood of the vertex $v\in V$. My question is: is it true that there also must exist a labeling of $G$ with labels $\{1,2,3\}$ such that for any two adjacent vertices $u$ and $w$, we have: $$\sum_{v\in N(u)}c(v)\neq \sum_{v\in N(w)}c(v)?$$

It is possible for two adjacent vertices to satisfy the first equation, but not the second in some labeling $c$. My idea was to modify the initial labeling in a way that makes the second inequality hold. That is, for some adjacent vertices $u$ and $w$ satisfying the first equation, if $\sum_{v\in N(u)}c(v)=\sum_{v\in N(w)}c(v)$ holds then $c(u)\neq c(w)$. Without loss of generality, we may assume that $c(u)<c(w)$. Then, change the label of $u$ to $c(w)$ thus obtaining the new labeling $c'$. However, this may affect the relationship of $u$ with its other neighbors and my attempts to analyze those weren't successful. I would really appreciate some help.

This question comes from reading the paper of Lason where he seems to claim that the second result is a consequence of the first (if I understand correctly what he means by the "special case").

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.