Hi, I don't know much about graph theory so I would need to know if the following problem has a positive answer or a reference. There is a bipartite graph G with the two vertex sets V1, V2. Each vertex of V1 is connected to a least 2 vertices of V2 and with at most N vertices of V2. Each vertex of V2 is connected with some vertex of V1. Is there a function f(N) such that choosing f(N) colors to color the vertices of V2 I can ensure that each vertex of V1 is connected with at least two vertices of different colors?
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Answer is NO. Consider the following bipartite graph $G=(V,E)$. $V(G)=\{ v_1, \ldots , v_n\}\cup \{u_{i,j}: 1 \leq i < j \leq n\}$, $E(G)=\{v_i u_{i,j}:1 \leq i \leq n , \, \, 1 \leq j \leq n\}$. Let $V_1=\{u_{i,j}: 1 \leq i < j \leq n\}$ and $V_2=\{ v_1, \ldots , v_n\}$. Each vertex in $V_1$ is connected to exactly two vertices in $V_2$, so $N=2$, but we need at least $n$ colors to color the vertices of $V_2$, to ensure that each vertex of $V_1$ is connected with at least two vertices of different colors. 

