Two remarks on circular arc graphs (Q675889)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Two remarks on circular arc graphs |
scientific article |
Statements
Two remarks on circular arc graphs (English)
0 references
18 August 1997
0 references
A graph \(G\) is said to be a circular arc graph if there exist circular arcs A\(g\), \(g\in V(G)\), such that \(g\), \(g'\) are adjacent in \(G\) if and only if the corresponding A\(g\), A\(_{g'}\) intersect. This paper shows that a graph with clique covering number two is a circular arc graph if and only if its edges can be coloured by two colours so that no induced four-cycle contains two opposite edges of the same colour.
0 references
clique covering number
0 references
circular arc graph
0 references
0 references
0 references
0 references