25 - 29 de Noviembre de 2002

Montevideo, Uruguay

Radisson Victoria Plaza Hotel

 
TM2
 
Bouchet Graphs: A Generalization of Circle Graph

Hernán Czemerinski
Departamento de Computación Facultad de Ciencias Exactas y Naturales UBA
hczemeri@dc.uba.ar
 
Abstract

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 André Bouchet in 1994. In this thesis, 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 also generalize interval graphs, 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 diferent formulations of Bouchet's characterization theorem for circle graphs.



Volver

infoUYclei 2002