On 3-coloring circle graphs
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.
- Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
- Embedding planar graphs in four pages
- Four pages are indeed necessary for planar graphs
- Graph-Theoretic Concepts in Computer Science
- scientific article; zbMATH DE number 4051024 (Why is no real title available?)
- scientific article; zbMATH DE number 52166 (Why is no real title available?)
- scientific article; zbMATH DE number 2159655 (Why is no real title available?)
- Planar graphs that need four pages
- Simpler algorithms for testing two-page book embedding of partitioned graphs
- Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph
- The complexity of colouring circle graphs (extended abstract)
This page was built for publication: On 3-coloring circle graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6636987)
