# Prove np-hardness of dividing items from the lists

I have the following problem.

Given a finite number of lists of items. The same item can appear in many lists. I would like to color items with 3 colors, such at least two colors appear in each list.

I would like to show that this problem is NP-hard. I would like to provide reduction from the 3-coloring problem which seems to be similar.

I think I could make items as nodes and link every item with every other from the shared lists, but then the condition of 3-coloring would be too demanding in comparison to my problem. What should I do differently in order to create the reduction?

• Try lists of size 2. – Yuval Filmus Jun 19 '18 at 20:44
• What do you mean? Items are not movable. – pw94 Jun 19 '18 at 21:13
• Are you trying to reduce in the wrong direction? – Yuval Filmus Jun 19 '18 at 21:13
• I hope I am not. I want to reduce from 3 coloring to my problem. Input to my problem are the lists of items to color. – pw94 Jun 19 '18 at 21:15
• Given an instance of 3-coloring, you need to produce an instance of your problem. – Yuval Filmus Jun 19 '18 at 21:16

So what we are trying to do, is to map every graph $$G(V,E)$$ to an instance of your problem, where every node $$v_i$$ will be mapped with an element $$el(v_i)$$ and every edge $$\epsilon\{v_1, v_2\}$$ would be represented with a two-element list $$\{el(v_1), el(v_2)\}$$.
So now a coloring $$f:V\rightarrow C$$ would be reduced to a coloring on the set of elements in your problem which means, if we found a coloring on the elements of the proposed problem, we can use the same coloring on our graph and it would be a proper coloring.
Proof. If $$f:V\rightarrow C$$ isn't a proper coloring, that means there is an edge with both nodes having the same color, which means there is a set with two elements and both of them have the same color which contradicts the statement of your problem.