# Scheduling problem on bipartite graph

Consider a bipartite graph $G=(U, V, E)$. Each $v \in V$ represents a soccer team, and each $u \in U$ represents a mini-tournament needs to be scheduled.

If $u_i$ and $u_j$ share no common neighbor, these two tournament can be scheduled on the same day. Similarly, one can schedule multiple tournaments in one day if there is no such conflict.

Is there a way to compute the minimum number of days required to complete all the tournaments and the corresponding scheduling?

• Welcome to CS.SE! What are your thoughts? What have you tried? We don't want to just do your exercise for you: we want you to gain understanding, but as you haven't given us much to work with, it's not clear how to help you. – D.W. Dec 10 '15 at 6:08
• Hi, thanks for your comment. I don't know much about graph theory. I was hoping that the problem I described here may be some form of a known problem, and people who are more knowledgeable on this topic can provide some reference. – user43498 Dec 10 '15 at 16:52

So here, it looks as though $u \in U$ is a vertex representing the team and $v \in V$ is an edge between the vertices representing the matches possible.
If we can generate a Bipartite Graph, the edges ${ v_i, ...v_j}$ going across are all non-conflicting matches. Those edges for this matching ( $M_1$) can be held on that day. Next, we remove ${ v_i, ...v_j}$ and check to see if we can get more Bipartite Graphs. The edges going across are similarly the non-conflicting matches.