1

What are the conditions that an undirected bipartite graph $G=(U,V, E)$ should have to be colored as follows:

Nodes in $U$ are colored $-1$ or $+1$. The sign of a node $v \in V$ is the sum of the colors of the nodes in $U$ connected to $v$, i.e. $c(v) = \sum_{(v,u)\in E}{c(u)}$. A coloring is valid only if $0 \le c(v) \le 1, \forall{v \in V}$.

For example if $|V| = 2$, then we can always have a valid coloring.

Any help on this is greatly appreciated.

Mostafa Dehghan
  • 11
  • A very similar question was asked a little while ago, I'll see if I can find it and link it. Where did this question come from? What are your thoughts so far about incomplete sets of necessary or sufficient conditions? – user2566092 Sep 21 '15 at 16:45
  • This is from a research problem I am trying to solve. So far I only have the $|V| = 2$ result. – Mostafa Dehghan Sep 21 '15 at 16:59
  • If it's a research problem, then sometimes computer experiments can be very helpful, compared to just banging your head against a wall trying to come up with the theorem. E.g. you could try $|V| = 3,4$ with all graphs with sets $U$ up to a certain somewhat small size, and see which graphs admit a valid coloring and see if you can find a pattern. – user2566092 Sep 21 '15 at 17:07

0 Answers0