Approximating minimum coloring and maximum independent set in dotted interval graphs

Dotted interval graphs are introduced by Aumann et al. as a generalization of interval graphs. We study two optimization problems in dotted interval graphs that find application in high-throughput genotyping. We present improved approximations for minimum coloring and the first approximation for maximum independent set in dotted interval graphs.