The Complexity of Coloring Circular Arcs and Chords
type: Item
instance of: scholarly article
title: The Complexity of Coloring Circular Arcs and Chords
zbMATH Open document ID: 0499.05058
DOI: 10.1137/0601025
author: M. R. Garey
author: D. S. Johnson
author: Gary L. Miller
author: Christos Papadimitriou
published in: SIAM Journal on Algebraic Discrete Methods
publication date: 1980-01-01T00:00:00Z
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 20F10
zbMATH DE Number: 3786840
zbMATH Keywords: word problem
zbMATH Keywords: circular arc graph coloring problem
zbMATH Keywords: circle graph coloring problem
zbMATH Keywords: NP-complete
Wikidata QID: Q55951939
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1137/0601025
OpenAlex ID: W2074937107
cites work: Q4091421
cites work: Q5684962
cites work: Some simplified NP-complete graph problems
cites work: Q4198056
cites work: Algorithms for a maximum clique and a maximum independent set of a circle graph
cites work: Algorithms on circular-arc graphs
cites work: On the Computational Complexity of Combinatorial Problems
cites work: Q4057549
cites work: Matrix characterizations of circular-arc graphs
cites work: Structure theorems for some circular-arc graphs
cites work: Coloring a Family of Circular Arcs
cites work: An Efficient Test for Circular-Arc Graphs
DBLP publication ID: journals/siammax/GareyJMP80
description: scientific article