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
-
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$– David Benson-PutninsCommented May 8, 2013 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$– Carl FeynmanCommented May 9, 2013 at 0:45
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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$ Commented Nov 19, 2013 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$ Commented Nov 20, 2013 at 10:50