The Complexity of Coloring Circular Arcs and Chords
From MaRDI portal
Publication:3964622
DOI10.1137/0601025zbMath0499.05058WikidataQ55951939 ScholiaQ55951939MaRDI QIDQ3964622
Christos H. Papadimitriou, David S. Johnson, Gary Lee Miller, Michael R. Garey
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
68Q25: Analysis of algorithms and problem complexity
05C15: Coloring of graphs and hypergraphs
20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
05C99: Graph theory
Related Items
Optimal on-line coloring of circular arc graphs, Efficient parallel recognition of some circular arc graphs. II, Independence and domination in polygon graphs, 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, Container ship stowage problem complexity and connection to the coloring of circle graphs, Jump number maximization for proper interval graphs and series-parallel graphs, Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs, Intersection graphs of Helly families of subtrees, Two-page book embedding of trees under vertex-neighborhood constraints
