# bipartite graph coloring

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?

• The number of colors that you are required to use is basically independent of N because of how little it affects the graph. Consider the following graph: I have a vertex in V1 connected to N vertices in V2. I also have a bunch of vertices in V1 which are connected to vertices in V2 that aren't from the original N. The number of colors required is essentially independent of N The number required can also be arbitrarily high. For the vertex set V2, for each pair of vertices put a vertex in V1 that connects to both of them. Then every vertex in V2 needs to be colored differently. May 8 '13 at 21:31
• For the case where all the V1 vertices have two neighbors, this reduces to vertex-coloring an arbitrary graph, with all its NP-complete goodness. The structure you are describing as "a bipartite graph with..." is more commonly called a hypergraph. V2 is the vertices of the hypergraph and V1 is the hyperedges. May 9 '13 at 0:45

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.