Circular-arc graphs with clique cover number two

DOI10.1016/0095-8956(88)90038-XzbMath0596.05042OpenAlexW1971826818MaRDI QIDQ1078197

Jeremy P. Spinrad

Publication date: 1988

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0095-8956(88)90038-x

zbMATH Keywords

dimensionrecognizing circular arc- graphstwo-dimensional partial orders

Mathematics Subject Classification ID

Partial orders, general (06A06) Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Related Items

Circular‐Arc Bigraphs and Its Subclasses ⋮ On orthogonal ray graphs ⋮ Recognizing simple-triangle graphs by restricted 2-chain subgraph cover ⋮ List-homomorphism problems on graphs and arc consistency ⋮ Permutation bigraphs and interval containments ⋮ New characterizations of proper interval bigraphs ⋮ On orthogonal ray trees ⋮ A simpler linear-time recognition of circular-arc graphs ⋮ Structural results on circular-arc graphs and circle graphs: a survey and the main open problems ⋮ Two remarks on circular arc graphs ⋮ List H-coloring a graph by removing few vertices ⋮ Obstacle numbers of graphs ⋮ Representation characterizations of chordal bipartite graphs ⋮ Interval \(k\)-graphs and orders ⋮ Characterizations and recognition of circular-arc graphs and subclasses: a survey ⋮ A generalization of the theorem of Lekkerkerker and Boland ⋮ Lexicographic Orientation Algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Characterization problems for graphs, partially ordered sets, lattices, and families of sets
• Structure theorems for some circular-arc graphs
• An Efficient Test for Circular-Arc Graphs
• Algorithms on circular-arc graphs
• Circular permutation graphs
• SOME APPLICATIONS OF GRAPH THEORY AND RELATED NON‐METRIC TECHNIQUES TO PROBLEMS OF APPROXIMATE SERIATION: THE CASE OF SYMMETRIC PROXIMITY MEASURES