On 3-Coloring Circle Graphs

Patricia Bachmann, Ignaz Rutter, Peter Stumpf

Given a graph $G$ with a fixed vertex order $\prec$, one obtains a circle graph $H$ whose vertices are the edges of $G$ and where two such edges are adjacent if and only if their e…