Partial characterizations of circle graphs

Mostrar todas las versiones(3)

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 ind...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Bonomo, F., Durán, G., Grippo, L.N., Safe, M.D.
Formato:	JOUR
Materias:	P 4-tidy graphs Circle graphs Helly circle graphs Linear domino graphs Tree-cographs Unit circle graphs <sup>P 4</sup>-tidy graphs Unit circles Graphic methods Plant extracts Trees (mathematics)
Acceso en línea:	http://hdl.handle.net/20.500.12110/paper_0166218X_v159_n16_p1699_Bonomo
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	todo:paper_0166218X_v159_n16_p1699_Bonomo
record_format	dspace
spelling	todo:paper_0166218X_v159_n16_p1699_Bonomo2023-10-03T15:03:38Z Partial characterizations of circle graphs Bonomo, F. Durán, G. Grippo, L.N. Safe, M.D. P 4-tidy graphs Circle graphs Helly circle graphs Linear domino graphs Tree-cographs Unit circle graphs <sup>P 4</sup>-tidy graphs Circle graphs Helly circle graphs Linear domino graphs Tree-cographs Unit circles Graphic methods Plant extracts Trees (mathematics) 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_0166218X_v159_n16_p1699_Bonomo
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	P 4-tidy graphs Circle graphs Helly circle graphs Linear domino graphs Tree-cographs Unit circle graphs <sup>P 4</sup>-tidy graphs Circle graphs Helly circle graphs Linear domino graphs Tree-cographs Unit circles Graphic methods Plant extracts Trees (mathematics)
spellingShingle	P 4-tidy graphs Circle graphs Helly circle graphs Linear domino graphs Tree-cographs Unit circle graphs <sup>P 4</sup>-tidy graphs Circle graphs Helly circle graphs Linear domino graphs Tree-cographs Unit circles Graphic methods Plant extracts Trees (mathematics) Bonomo, F. Durán, G. Grippo, L.N. Safe, M.D. Partial characterizations of circle graphs
topic_facet	P 4-tidy graphs Circle graphs Helly circle graphs Linear domino graphs Tree-cographs Unit circle graphs <sup>P 4</sup>-tidy graphs Circle graphs Helly circle graphs Linear domino graphs Tree-cographs Unit circles Graphic methods Plant extracts Trees (mathematics)
description	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.
format	JOUR
author	Bonomo, F. Durán, G. Grippo, L.N. Safe, M.D.
author_facet	Bonomo, F. Durán, G. Grippo, L.N. Safe, M.D.
author_sort	Bonomo, F.
title	Partial characterizations of circle graphs
title_short	Partial characterizations of circle graphs
title_full	Partial characterizations of circle graphs
title_fullStr	Partial characterizations of circle graphs
title_full_unstemmed	Partial characterizations of circle graphs
title_sort	partial characterizations of circle graphs
url	http://hdl.handle.net/20.500.12110/paper_0166218X_v159_n16_p1699_Bonomo
work_keys_str_mv	AT bonomof partialcharacterizationsofcirclegraphs AT durang partialcharacterizationsofcirclegraphs AT grippoln partialcharacterizationsofcirclegraphs AT safemd partialcharacterizationsofcirclegraphs
_version_	1807320844810059776

Partial characterizations of circle graphs

Ejemplares similares