TY - JOUR
AU - Bachmann, Patricia
AU - Rutter, Ignaz
AU - Stumpf, Peter
PY - 2024/10/28
Y2 - 2024/11/08
TI - On 3-Coloring Circle Graphs
JF - Journal of Graph Algorithms and Applications
JA - JGAA
VL - 28
IS - 1
SE -
DO - 10.7155/jgaa.v28i1.2991
UR - https://jgaa.info/index.php/jgaa/article/view/2991
SP - 389-402
AB - <pre>Given a graph $G$ with a fixed vertex order $\prec$, one obtains a circle graph $H$ whose vertices are the</pre><pre> edges of $G$ and where two such edges are adjacent if and only if their endpoints are pairwise distinct and</pre><pre> alternate in $\prec$.</pre><pre> Therefore, the problem of determining whether $G$ has a $k$-page book embedding with spine order $\prec$ is</pre><pre> equivalent to deciding whether $H$ can be colored with $k$ colors.</pre><pre> Finding a $k$-coloring for a circle graph is known to be NP-complete for $k \geq 4$ [9] and trivial for $k \leq 2$.</pre><pre> For $k = 3$, Unger (1992) claims an efficient algorithm that finds a 3-coloring in $O(n \log n)$ time, if it</pre><pre> exists.</pre><pre> Given a circle graph $H$, Unger's algorithm (1) constructs a 3-\textsc{Sat} formula $\Phi$ that is</pre><pre> satisfiable if and only if $H$ admits a 3-coloring and (2) solves $\Phi$ by a backtracking strategy that</pre><pre> relies on the structure imposed by the circle graph.</pre><pre> However, the extended abstract misses several details and Unger refers to his PhD thesis (in German) for</pre><pre> details.</pre><pre> </pre><pre> In this paper we argue that Unger's algorithm for 3-coloring circle graphs is not correct and that</pre><pre> 3-coloring circle graphs should be considered as an open problem.</pre><pre> We show that step (1) of Unger's algorithm is incorrect by exhibiting a circle graph and its representation whose</pre><pre> formula $\Phi$ is satisfiable but that is not 3-colorable.</pre><pre> We further show that Unger's backtracking strategy for solving</pre><pre> $\Phi$ in step (2) may produce incorrect results and give empirical evidence that</pre><pre> it exhibits a runtime behaviour that is not consistent with the claimed running time.</pre>
ER -