The complexity of colouring circle graphs (extended abstract)
DOI10.1007/3-540-55210-3_199zbMATH Open1494.68204OpenAlexW2135326066WikidataQ55951940 ScholiaQ55951940MaRDI QIDQ5096797FDOQ5096797
Authors: Walter Unger 
Publication date: 18 August 2022
Published in: STACS 92 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-55210-3_199
Recommendations
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)
Cites Work
- Efficient algorithms for interval graphs and circular-arc graphs
- The Complexity of Coloring Circular Arcs and Chords
- Recognition of Circle Graphs
- Algorithms for a maximum clique and a maximum independent set of a circle graph
- Reconnaissance des graphes de cordes
- Reducing prime graphs and recognizing circle graphs
- Recognizing circle graphs in polynomial time
- Title not available (Why is that?)
- A characterization of circle graphs
- Title not available (Why is that?)
- An Efficient Test for Circular-Arc Graphs
- An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
- Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
- Finding maximum cliques in circle graphs
- Title not available (Why is that?)
- Orientations of circle graphs
- Title not available (Why is that?)
Cited In (21)
- On 3-coloring circle graphs
- Parameterized domination in circle graphs
- Approximating the minimum clique cover and other hard problems in subtree filament graphs
- Sorting with networks of data structures
- Title not available (Why is that?)
- Parameterized algorithms for book embedding problems
- 2-stack sorting is polynomial
- Upward book embeddings of st-graphs
- Upward book embeddability of \(st\)-graphs: complexity and algorithms
- Fixed-order book thickness with respect to the vertex-cover number: new observations and further analysis
- Parameterized algorithms for book embedding problems
- On fixed-order book thickness parameterized by the pathwidth of the vertex ordering
- Container ship stowage problem complexity and connection to the coloring of circle graphs
- On 3-coloring circle graphs
- Improved bounds for colouring circle graphs
- Parameterized analysis and crossing minimization problems
- 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
- Title not available (Why is that?)
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)
