A circle graph is an intersection graph of chords in a circle. These graphs have been introduced by Even and Itai in 1971 and were extensively studied. There are several characterizations for this class. One of them uses the concept of local complementations and was proposed by Andre Bouchet in 1994. In this work, we use the idea of this characterization to define a new class which generalizes circle graphs, and we call it Bouchet graphs. We prove that these graphs generalize interval graphs too and we find a characterization of the new class by 33 forbidden subgraphs, which is obtained by using a computer program. As a consequence of this characterization, we show that Bouchet graphs can be recognized in polynomial time. Finally, it is proved that there are 396 different formulations of Bouchet's characterization theorem for circle graphs.
展开▼
