Circular-arc graphs with clique cover number two
type: Item
instance of: scholarly article
title: Circular-arc graphs with clique cover number two
zbMATH Open document ID: 0596.05042
DOI: 10.1016/0095-8956(88)90038-X
published in: Journal of Combinatorial Theory. Series B
publication date: 1988-01-01T00:00:00Z
review text: The problem of recognizing circular-arc graphs which can be partitioned into two cliques is reduced to the problem of recognizing whether certain partial orders are two dimensional. This simplifies Tucker's algorithm for recognizing circular-arc graphs.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 3959471
zbMATH Keywords: dimension
zbMATH Keywords: two-dimensional partial orders
zbMATH Keywords: recognizing circular arc- graphs
author: Jeremy P. Spinrad
MaRDI profile type: Publication
cites work: Algorithms on circular-arc graphs
cites work: Q3328583
cites work: SOME APPLICATIONS OF GRAPH THEORY AND RELATED NON‐METRIC TECHNIQUES TO PROBLEMS OF APPROXIMATE SERIATION: THE CASE OF SYMMETRIC PROXIMITY MEASURES
cites work: Circular permutation graphs
cites work: Q3670598
cites work: An Efficient Test for Circular-Arc Graphs
cites work: Structure theorems for some circular-arc graphs
cites work: Characterization problems for graphs, partially ordered sets, lattices, and families of sets
full work available at URL: 0095-8956(88)90038-x
OpenAlex ID: W1971826818
description: scientific article; zbMATH DE number 3959471