The complexity of colouring circle graphs

DOI10.1007/3-540-55210-3_199zbMath1494.68204OpenAlexW2135326066WikidataQ55951940 ScholiaQ55951940MaRDI QIDQ5096797

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

zbMATH Keywords

computational complexitygraph colouringcircle graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (14)

2-stack sorting is polynomial ⋮ Parameterized analysis and crossing minimization problems ⋮ Sorting with networks of data structures ⋮ On polygon numbers of circle graphs and distance hereditary graphs ⋮ Upward book embeddability of \(st\)-graphs: complexity and algorithms ⋮ Parameterized algorithms for book embedding problems ⋮ Parameterized domination in circle graphs ⋮ On the complexity of container stowage planning problems ⋮ Parameterized Algorithms for Book Embedding Problems ⋮ Approximating the minimum clique cover and other hard problems in subtree filament graphs ⋮ On fixed-order book thickness parameterized by the pathwidth of the vertex ordering ⋮ Upward Book Embeddings of st-Graphs ⋮ Container ship stowage problem complexity and connection to the coloring of circle graphs ⋮ Fixed-order book thickness with respect to the vertex-cover number: new observations and further analysis

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A characterization of circle graphs
• Reconnaissance des graphes de cordes
• Reducing prime graphs and recognizing circle graphs
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
• An Efficient Test for Circular-Arc Graphs
• Finding maximum cliques in circle graphs
• Efficient algorithms for interval graphs and circular-arc graphs
• Orientations of circle graphs
• An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
• The Complexity of Coloring Circular Arcs and Chords
• Recognition of Circle Graphs
• Recognizing circle graphs in polynomial time
• Algorithms for a maximum clique and a maximum independent set of a circle graph

This page was built for publication: The complexity of colouring circle graphs