Dotted interval graphs
Yonatan Aumann, Moshe Lewenstein, Oren Melamud, Ron Y. Pinter, Zohar Yakhini · ACM Transactions on Algorithms · 2012
We introduce a generalization of interval graphs, which we call Dotted Interval Graphs (DIG). A dotted interval graph is an intersection graph of arithmetic progressions (dotted intervals). Coloring of dotted interval graphs naturally arises in the context of high throughput genotyping. We study the properties of dotted interval graphs, with a focus on coloring. We show that any graph is a DIG, but that DIG d graphs, that is, DIGs in which the arithmetic progressions have a jump of at most d , form a strict hierarchy. We show that coloring DIG d graphs is NP-complete even for d = 2. For any fixed d , we provide a 5/6 d + o ( d ) approximation for the coloring of DIG d graphs. Finally, we show that finding the maximal clique in DIG d graphs is fixed parameter tractable in d .