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?

  • 2
    $\begingroup$ 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. $\endgroup$ May 8 '13 at 21:31
  • 3
    $\begingroup$ 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. $\endgroup$ 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.

  • $\begingroup$ Is this answering the question? It doesn't seem clear to some of our readers that it does. $\endgroup$
    – Todd Trimble
    Nov 19 '13 at 20:13
  • $\begingroup$ Your edit is fine; I'd suggest you remove all the extraneous material, starting at "For more information ...". It's a bit off-putting that you cited your own not-exactly-relevant paper as your original answer, and I think this part would be best removed. $\endgroup$ Nov 20 '13 at 10:50

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.