Approximation algorithm for coloring of dotted interval graphs

Dotted interval graphs were introduced by Aumann et al. [Y. Aumann, M. Lewenstein, O. Melamud, R. Pinter, Z. Yakhini, Dotted interval graphs and high throughput genotyping, in: ACM-SIAM Symposium on Discrete Algorithms. SODA 2005, pp. 339-348] as a generalization of interval graphs. The problem of coloring these graphs found application in high-throughput genotyping. Jiang [M. Jiang, Approximating minimum coloring and maximum independent set in dotted interval graphs, Information Processing Letters 98 (2006) 29-33] improves the approximation ratio of Aumann et al. [Y. Aumann, M. Lewenstein, O. Melamud, R. Pinter, Z. Yakhini, Dotted interval graphs and high throughput genotyping, in: ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, pp. 339-348]. In this work we improve the approximation ratio of Jiang [M. Jiang, Approximating minimum coloring and maximum independent set in dotted interval graphs, Information Processing Letters 98 (2006) 29-33] and Aumarm et al. [Y. Aumann, M. Lewenstein, O. Melamud, R. Pinter, Z. Yakhini, Dotted interval graphs and high throughput genotyping, in: ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, pp. 339-348]. In the exposition we develop a generalization of the problem of finding the maximum number of non-attacking queens on a triangle. (c) 2008 Elsevier B.V. All rights reserved.