DIMACS TR: 2002-48
Consensus List Colorings of Graphs and Physical Mapping of DNA
Authors: N. V. R. Mahadev and Fred S. Roberts
ABSTRACT
In graph coloring, one assigns a color to each vertex of a graph so
that neighboring vertices get different colors. We shall talk about a
bioconsensus problem relating to graph coloring and discuss the
applicability of the ideas to the DNA physical mapping problem. In
many applications of graph coloring, one gathers data about the
acceptable colors at each vertex. A list coloring is a graph coloring
so that the color assigned to each vertex belongs to the list of
acceptable colors associated with that vertex. We consider the
situation where a list coloring cannot be found. If the data
contained in the lists associated with each vertex are made available
to individuals associated with the vertices, it is possible that the
individuals can modify their lists through trades or exchanges until
the group of individuals reaches a set of lists for which a list
coloring exists. We describe several models under which such a
consensus set of lists might be attained. In the physical mapping
application, the lists consist of the sets of possible copies of a
target DNA molecule from which a given clone was obtained and trades
or exchanges correspond to correcting errors in data.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-48.ps.gz
DIMACS Home Page