Edge Constrained Vertex Colorings and their Applications to Genomics

Edge Constrained Vertex Coloring (ECVC) problems are defined on a finite multigraph, their solutions are characterized, and a linear time algorithm is given for solving a $n$ ECVCs on the same underlying multigraph. Using ECVC problems we develop a novel family-based haplotype reconstruction method which has linear-time complexity in both number of markers and family size and has many other desirable properties.