  We consider the fair allocation of indivisible items to several agents with
additional conflict constraints. These are represented by a conflict graph
where each item corresponds to a vertex of the graph and edges in the graph
represent incompatible pairs of items which should not be allocated to the same
agent. This setting combines the issues of Partition and Independent Set and
can be seen as a partial coloring of the conflict graph. In the resulting
optimization problem each agent has its own valuation function for the profits
of the items. We aim at maximizing the lowest total profit obtained by any of
the agents. In a previous paper this problem was shown to be strongly \NP-hard
for several well-known graph classes, e.g., bipartite graphs and their line
graphs. On the other hand, it was shown that pseudo-polynomial time algorithms
exist for the classes of chordal graphs, cocomparability graphs, biconvex
bipartite graphs, and graphs of bounded treewidth. In this contribution we
extend this line of research by developing pseudo-polynomial time algorithms
that solve the problem for the class of convex bipartite conflict graphs,
graphs of bounded clique-width, and graphs of bounded tree-independence number.
The algorithms are based on dynamic programming and also permit fully
polynomial-time approximation schemes (FPTAS).
