The complexity of colouring circle graphs (extended abstract)
From MaRDI portal
Publication:5096797
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62)
Recommendations
Cites work
- scientific article; zbMATH DE number 3970805 (Why is no real title available?)
- 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 3997838 (Why is no real title available?)
- A characterization of circle graphs
- Algorithms for a maximum clique and a maximum independent set of a circle graph
- An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
- An Efficient Test for Circular-Arc Graphs
- Efficient algorithms for interval graphs and circular-arc graphs
- Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
- Finding maximum cliques in circle graphs
- Orientations of circle graphs
- Recognition of Circle Graphs
- Recognizing circle graphs in polynomial time
- Reconnaissance des graphes de cordes
- Reducing prime graphs and recognizing circle graphs
- The Complexity of Coloring Circular Arcs and Chords
Cited in
(21)- Parameterized domination in circle graphs
- On 3-coloring circle graphs
- Approximating the minimum clique cover and other hard problems in subtree filament graphs
- Sorting with networks of data structures
- scientific article; zbMATH DE number 4051024 (Why is no real title available?)
- Parameterized algorithms for book embedding problems
- 2-stack sorting is polynomial
- Upward book embeddings of st-graphs
- Fixed-order book thickness with respect to the vertex-cover number: new observations and further analysis
- Upward book embeddability of \(st\)-graphs: complexity and algorithms
- On fixed-order book thickness parameterized by the pathwidth of the vertex ordering
- Parameterized algorithms for book embedding problems
- Container ship stowage problem complexity and connection to the coloring of circle graphs
- On 3-coloring circle graphs
- Parameterized analysis and crossing minimization problems
- Improved bounds for colouring circle graphs
- On polygon numbers of circle graphs and distance hereditary graphs
- On the exact complexity of Hamiltonian Cycle and \(q\)-Colouring in disk graphs
- On the complexity of container stowage planning problems
- Coloring circle graphs
- scientific article; zbMATH DE number 52166 (Why is no real title available?)
This page was built for publication: The complexity of colouring circle graphs (extended abstract)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5096797)
