A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs
By: Ajaykrishnan E S , Robert Ganian , Daniel Lokshtanov and more
Potential Business Impact:
Colors circle graphs with three colors.
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.
Similar Papers
Graph Coloring Below Guarantees via Co-Triangle Packing
Data Structures and Algorithms
Colors graphs with fewer colors than usually possible.
On the structure of ($4K_1$, $C_4$, $P_6$)-free graphs
Discrete Mathematics
Helps computers color maps faster.
Coloring 3-Colorable Graphs with Low Threshold Rank
Data Structures and Algorithms
Finds colors for many parts of a tricky puzzle.