# Graphclass: circular arc

Definition:

A circular arc graph is the intersection graph of arcs of a circle.

### Open problems

1. Characterize circular arc graphs by forbidden induced subgraphs . A forbidden structure characterisation in the form of mutually avoiding walks is given in .
2. Characterize circular arc graphs that admit a model where the arcs have to most two sizes .
3. Characterize circular arc bigraphs (see interval bigraph ) .

;

## Inclusions

The map shows the inclusions between the current class and a fixed set of landmark classes. Minimal/maximal is with respect to the contents of ISGCI. Only references for direct inclusions are given. Where no reference is given, check equivalent classes or use the Java application. To check relations other than inclusion (e.g. disjointness) use the Java application, as well.

[+]Details

[+]Details

[+]Details

## Problems

Problems in italics have no summary page and are only listed when ISGCI contains a result for the current class.

3-Colourability Polynomial [+]Details
Clique Polynomial [+]Details
Clique cover Linear [+]Details
Cliquewidth Unbounded [+]Details
Cliquewidth expression Unbounded or NP-complete [+]Details
Colourability NP-complete [+]Details
Cutwidth Unknown to ISGCI [+]Details
Domination Linear [+]Details
Feedback vertex set Polynomial [+]Details
Graph isomorphism Unknown to ISGCI [+]Details
Hamiltonian cycle Polynomial [+]Details
Hamiltonian path Polynomial [+]Details
Independent dominating set Unknown to ISGCI [+]Details
Independent set Linear [+]Details
Maximum cut Unknown to ISGCI [+]Details
Recognition Linear [+]Details
Treewidth Polynomial [+]Details
Weighted clique Polynomial [+]Details
Weighted feedback vertex set Polynomial [+]Details
Weighted independent dominating set Unknown to ISGCI [+]Details
Weighted independent set Polynomial [+]Details
Weighted maximum cut NP-complete [+]Details