Some results on a trading model in a consensus list coloring
Damain Bogdanowicz, Krzysztof Giaro · 2008
Let S(v) denote a nonempty set of integers assigned to vertex v of graph G = (V, E). Let us call S a list assignment for G. We look for a legal graph coloring f such that for every vertex v isin V we have f(v) isin S(v). A trade from a vertex u to v means that we remove color c from S(u) and add it to S(v). In the trading model we ask how many trades are required in order to obtain a list assignment that has a list coloring. So (G, S) is p-tradeable if this can be done in p or fewer trades. We show a polynomial algorithm for determining the minimal p for complete graphs. An analogous problem for trees is NP-hard. However, it is polynomial for partial k-trees with fixed k and fixed total number of colors.