The Complexity of Coloring Circular Arcs and Chords

DOI10.1137/0601025MaRDI QIDQ3964622zbMATH OpenOpenAlexDBLPWikidataFDO

Authors M. R. Garey, D. S. Johnson, Gary L. Miller, Christos Papadimitriou

Publication date 1980

Published in SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0601025

zbMATH Keywords

circle graph coloring problemcircular arc graph coloring problemNP-completeword problem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph theory (05C99) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Analysis of algorithms and problem complexity (68Q25)

Cites work

• Algorithms for a maximum clique and a maximum independent set of a circle graph
• Algorithms on circular-arc graphs
• An Efficient Test for Circular-Arc Graphs
• Coloring a Family of Circular Arcs
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3420624 (Why is no real title available?)
• Matrix characterizations of circular-arc graphs
• On the Computational Complexity of Combinatorial Problems
• Some simplified NP-complete graph problems
• Structure theorems for some circular-arc graphs

Cited in

(only showing first 100 items - show all)

• Mutual exclusion scheduling with interval graphs or related classes. I
• Minimum entropy coloring
• Hadwiger's conjecture for proper circular arc graphs
• Efficient algorithms for wavelength assignment on trees of rings
• Weighted coloring: further complexity and approximability results
• APX-hardness of domination problems in circle graphs
• An O(qn) algorithm to q-color a proper family of circular arcs
• On the chromatic number of multiple interval graphs and overlap graphs
• Dominating sets and domatic number of circular arc graphs
• Algorithmic aspects of intersection graphs and representation hypergraphs
• Embedding planar graphs in four pages
• Representations of graphs and networks (coding, layouts and embeddings)
• Precoloring extension. I: Interval graphs
• Efficient parallel recognition of some circular arc graphs. I
• All structured programs have small tree width and good register allocation
• A weighted graph polynomial from chromatic invariants of knots
• Algorithms for preemptive scheduling of different classes of processors to do jobs with fixed times
• A simple optimal parallel algorithm for the minimum coloring problem on interval graphs
• The k-track assignment problem
• Periodic assignment and graph colouring
• Cyclic scheduling in a robotic production line
• The permutation-path coloring problem on trees.
• Induced matchings in intersection graphs.
• Container ship stowage problem complexity and connection to the coloring of circle graphs
• Splittable traffic partition in WDM/SONET rings to minimize SONET ADMs
• Routing and path multicoloring
• List matrix partitions of graphs representing geometric configurations
• Conversion of coloring algorithms into maximum weight independent set algorithms
• Jump number maximization for proper interval graphs and series-parallel graphs
• An \(0(n^{1.5})\) algorithm to color proper circular arcs
• The longest common subsequence problem for sequences with nested arc annotations.
• Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs
• Intersection graphs of Helly families of subtrees
• On parameterized algorithms for fixed-order book thickness with respect to the pathwidth of the vertex ordering
• Revising Johnson's table for the 21st century
• Distributed interactive proofs for the recognition of some geometric intersection graph classes
• Fixed-order book thickness with respect to the vertex-cover number: new observations and further analysis
• Strong edge coloring of circle graphs
• The chromatic index of proper circular-arc graphs of odd maximum degree which are chordal
• A survey on book-embedding of planar graphs
• 2-nested matrices: towards understanding the structure of circle graphs
• Hardness and approximation for L-EPG and \(B_1\)-EPG graphs
• Planar graphs that need four pages
• Local and union page numbers
• List k-colouring P_t-free graphs: a mim-width perspective
• Two-page book embedding of trees under vertex-neighborhood constraints
• Subtree filament graphs are subtree overlap graphs
• Routing equal-size messages on a slotted ring
• The complexity of register allocation
• Computing and counting longest paths on circular-arc graphs in polynomial time
• Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
• Routing permutations and involutions on optical ring networks: Complexity results and solution to an open problem
• A short proof of the NP-completeness of minimum sum interval coloring
• Approximating the minimum clique cover and other hard problems in subtree filament graphs
• Perfect circular arc coloring
• Independent packings in structured graphs
• On some applications of the selective graph coloring problem
• Succinct encodings for families of interval graphs
• On the minimum and maximum selective graph coloring problems in some graph classes
• Compact representation of interval graphs and circular-arc graphs of bounded degree and chromatic number
• On algorithmic applications of sim-width and mim-width of (H₁,H₂)-free graphs
• Revisiting Tucker's algorithm to color circular-arc graphs
• String graphs of k-bend paths on a grid
• On inverse chromatic number problems (extended abstract)
• A note on optical routing on trees
• Minimum weight feedback vertex sets in circle n-gon graphs and circle trapezoid graphs
• Parameterized maximum path coloring
• Algorithms for Necklace Maps
• Embedding generalized Petersen graph in books
• SUB-COLORING AND HYPO-COLORING INTERVAL GRAPHS
• Inverse chromatic number problems in interval and permutation graphs
• Exact and heuristic approaches to the airport stand allocation problem
• Max point-tolerance graphs
• Embedding Outerplanar Graphs in Small Books
• Parameterized maximum path coloring
• An O(n^2 ) Algorithm for Coloring Proper Circular Arc Graphs
• Optimization problems in dotted interval graphs
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• Optimal on-line coloring of circular arc graphs
• More applications of the d-neighbor equivalence: acyclicity and connectivity constraints
• Improved bounds for colouring circle graphs
• The complexity of colouring circle graphs (extended abstract)
• On the size of outer-string representations
• On the L(h, k)‐labeling of co‐comparability graphs and circular‐arc graphs
• Selfish Routing and Path Coloring in All-Optical Networks
• On the complexity of interval scheduling with a resource constraint
• On coloring problems with local constraints
• Exploring the complexity boundary between coloring and list-coloring
• On rectangle intersection graphs with stab number at most two
• Complexity and online algorithms for minimum skyline coloring of intervals
• The complexity of path coloring and call scheduling
• An approximation result for a periodic allocation problem
• Circular-arc graph coloring: On chords and circuits in the meeting graph
• Extending partial representations of circular-arc graphs
• Bounding the mim‐width of hereditary graph classes
• Maximum max-k-clique subgraphs in cactus subtree graphs
• Treewidth versus clique number. II: Tree-independence number
• On \(d\)-stable locally checkable problems parameterized by mim-width
• A (1.5+)-approximation algorithm for weighted connectivity augmentation
• The optimal cost chromatic partition problem for trees and interval graphs

This page was built for publication: The Complexity of Coloring Circular Arcs and Chords

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3964622)