{"ID":2842996,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.09707","arxiv_id":"2511.09707","title":"A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs","abstract":"A graph $G$ is a circle graph if it is an intersection graph of chords of a unit circle. We give an algorithm that takes as input an $n$ vertex circle graph $G$, runs in time at most $n^{O(\\log n)}$ and finds a proper $3$-coloring of $G$, if one exists. As a consequence we obtain an algorithm with the same running time to determine whether a given ordered graph $(G, \\prec)$ has a $3$-page book embedding. This gives a partial resolution to the well known open problem of Dujmović and Wood [Discret. Math. Theor. Comput. Sci. 2004], Eppstein [2014], and Bachmann, Rutter and Stumpf [J. Graph Algorithms Appl. 2024] of whether 3-Coloring on circle graphs admits a polynomial time algorithm.","short_abstract":"A graph $G$ is a circle graph if it is an intersection graph of chords of a unit circle. We give an algorithm that takes as input an $n$ vertex circle graph $G$, runs in time at most $n^{O(\\log n)}$ and finds a proper $3$-coloring of $G$, if one exists. As a consequence we obtain an algorithm with the same running time...","url_abs":"https://arxiv.org/abs/2511.09707","url_pdf":"https://arxiv.org/pdf/2511.09707v1","authors":"[\"Ajaykrishnan E S\",\"Robert Ganian\",\"Daniel Lokshtanov\",\"Vaishali Surianarayanan\"]","published":"2025-11-12T20:10:16Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CG\"]","methods":"[]","has_code":false}