Before revision:  Hence, every feasible allocation of items to the agents corresponds to a partial coloring , that is , a collection of pairwise disjoint independent sets. The sum of profits of vertices/items assigned to one color/agent should be optimized in a maxi-min sense. We derive complexity and algorithmic results for this problem , which is a generalization of the classical Partitionand Independent Set problems. In particular, we{\sc  {\sc   show that the problem is strongly NP-complete in the classes of bipartite graphs and their line graphs, and solvable in pseudo-polynomial time in the classes of cocomparability graphs and biconvex bipartite graphs  .
After revision:  Hence, every feasible allocation of items to the agents corresponds to a partial coloring of the conflict graph. Every agent has its own profit valuation for every item. Aiming at a fair allocation, our goal is the maximization of the lowest total profit of items allocated to any one of the agents. The resulting optimization problem contains, as special cases, both{\sc {\sc show that the problem is strongly NP-complete in the classes of bipartite graphs and their line graphs, and solvable in pseudo-polynomial time in the classes of cocomparability graphs and biconvex bipartite graphs .