# Breaking frustrated loops in list coloring problem

Suppose we have a graph with $n$ vertices and $n$ lists of colors such that no vertex coloring of the graph using colors from given lists is a proper list coloring. We can characterize the obstacle to proper list coloring in terms of frustrated cycles -- simple cycles such that every list coloring of the induced subgraph is improper.

Given graph and set of color lists I'd like to delete a small number of vertices to break a large number of frustrated cycles.

-
If (a few) lists of size 1 are allowed, there are also interesting examples of trees with no proper list coloring. It might be a good idea for you to provide some examples so that "small", "large", are made clear. Also a few words on the obstacle characterization would be appreciated. Do you want to eventually break all cycles? Or are you content with a maximal colorable subgraph? Also, it would help if you contrasted your problem with known literature, so that experts can suggest alternatives that you want. Gerhard "Ask Me About System Design" Paseman, 2011.01.09 –  Gerhard Paseman Jan 10 '11 at 4:30
I unfortunately don't know any related literature, this is a theoretical example for a practical problem that arises when running a particular message passing algorithm on graph. Frustrated cycles cause convergence problems and I can delete a few nodes and correct for their removal. There's a bounded number of nodes I can afford to remove, so I want to break as many frustrated cycles as possible with that number. –  Yaroslav Bulatov Jan 10 '11 at 19:07
It sounds like you are asking if the Erdős–Pósa property holds for frustrated cycles. That is, does there exists a function $f: \mathbb{N} \to \mathbb{N}$, such that every graph (with lists) either has $k$ disjoint frustrated cycles, or a set of vertices $X$, of size at most $f(k)$, such that $G -X$ contains no frustrated cycles.