Restricted circular-arc graphs and clique cycles Original Research Article

Circular-arc graphs are natural analogs of chordal and interval graphs, but without some of the features that make chordal and interval graphs particularly nice; perhaps, the biggest difference is the failure of the Helly condition. Restricting circular-arc representations so as to have no three or fewer arcs cover the entire circle and to have the endpoints of arcs be distinguishable by other arcs results in a notion of ‘restricted circular-arc graphs’ that enjoys many of the nice features of chordal graphs. Their theory is surprisingly parallel to that of chordal graphs, substituting ‘clique cycles’ for clique trees, but they also have several distinctive features and characterizations.