Partial characterizations of circle graphs

En:

Discrete Appl Math 2011;159(16):1699-1706

Fecha:

2011

Formato:

application/pdf

Tipo de documento:

info:eu-repo/semantics/article
info:ar-repo/semantics/artículo
info:eu-repo/semantics/publishedVersion

Descriptores:

P 4-tidy graphs -  Circle graphs -  Helly circle graphs -  Linear domino graphs -  Tree-cographs -  Unit circle graphs -  ^{P 4}-tidy graphs -  Circle graphs -  Helly circle graphs

Descripción:

A circle graph is the intersection graph of a family of chords on a circle. There is no known characterization of circle graphs by forbidden induced subgraphs that do not involve the notions of local equivalence or pivoting operations. We characterize circle graphs by a list of minimal forbidden induced subgraphs when the graph belongs to one of the following classes: linear domino graphs, P4-tidy graphs, and tree-cographs. We also completely characterize by minimal forbidden induced subgraphs the class of unit Helly circle graphs, which are those circle graphs having a model whose chords have all the same length, are pairwise different, and satisfy the Helly property. © 2010 Elsevier B.V. All rights reserved.
Fil:Bonomo, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.
Fil:Durán, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.
Fil:Grippo, L.N. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.
Fil:Safe, M.D. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.

Identificador(es):

http://hdl.handle.net/20.500.12110/paper_0166218X_v159_n16_p1699_Bonomo

Derechos:

info:eu-repo/semantics/openAccess
http://creativecommons.org/licenses/by/2.5/ar