|
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.
|
|
Texto completo
Volver
|
|
infoUYclei 2002
|
|