Academic
Publications
Some results on a trading model in a consensus list coloring

Some results on a trading model in a consensus list coloring,10.1109/INFTECH.2008.4621644,Damain Bogdanowicz,Krzysztof Giaro

Some results on a trading model in a consensus list coloring   (Citations: 1)
BibTex | RIS | RefWorks Download
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.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: