Two remarks on circular arc graphs

DOI10.1007/BF01202237zbMath0868.05043OpenAlexW2042309505MaRDI QIDQ675889

Pavol Hell, Jing Huang

Publication date: 18 August 1997

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01202237

zbMATH Keywords

circular arc graphclique covering number

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75)

Related Items (13)

Ferrers dimension of grid intersection graphs ⋮ Circular‐Arc Bigraphs and Its Subclasses ⋮ Recognizing simple-triangle graphs by restricted 2-chain subgraph cover ⋮ On orthogonal ray trees ⋮ Structural results on circular-arc graphs and circle graphs: a survey and the main open problems ⋮ Non-edge orientation and vertex ordering characterizations of some classes of bigraphs ⋮ Obstacle numbers of graphs ⋮ Representation characterizations of chordal bipartite graphs ⋮ Characterizations and recognition of circular-arc graphs and subclasses: a survey ⋮ A generalization of the theorem of Lekkerkerker and Boland ⋮ Lexicographic Orientation Algorithms ⋮ Partial Characterizations of 1‐Perfectly Orientable Graphs ⋮ Graphs and digraphs represented by intervals and circular arcs

Cites Work

• Unnamed Item
• Unnamed Item
• Circular-arc graphs with clique cover number two
• Finding maximum cliques on circular-arc graphs
• An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs
• Characterization problems for graphs, partially ordered sets, lattices, and families of sets
• List homomorphisms and circular arc graphs
• Matrix characterizations of circular-arc graphs
• Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
• An Efficient Test for Circular-Arc Graphs
• Algorithms on circular-arc graphs
• Coloring a Family of Circular Arcs
• $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
• Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs
• A Linear Algorithm for Maximum Weight Cliques in Proper Circular Arc Graphs
• Transitiv orientierbare Graphen

This page was built for publication: Two remarks on circular arc graphs