On 3-coloring circle graphs (Q6636987)

Finding a \(k\)-coloring for a circle graph is known to be NP-complete for \(k \ge 4\) and trivial for \(k=1,2\). In 1992, \textit{W. Unger} [Lect. Notes Comput. Sci. 577, 389--400 (1992; Zbl 1494.68204)] claimed to have an efficient algorithm that finds a 3-coloring in \(O(n\log n)\) time if it exists. Much of the detail for Unger's paper is in his PhD thesis, which is in German [\textit{W. Unger}, Färbung von Kreissehnengraphen (Coloring of circle string graphs). University of Paderborn, Germany (PhD Thesis) \N(1990)]. Here the authors argue that there are errors in Unger's algorithm, both in the transformation of the 3-coloring problem to a satisfiability problem and with empirical evidence that exhibits a runtime behavior that is not consistent with the claimed running time.