Question on Vertex Labeling (Related to Lucky Labeling of Graphs)

117 Views Asked by At

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").