Partial characterizations of circle graphs

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, Flavia, Durán, Guillermo A., Grippo, Luciano Norberto, Safe, Martín Darío
Publicado:	2011
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:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v159_n16_p1699_Bonomo 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	paper:paper_0166218X_v159_n16_p1699_Bonomo
record_format	dspace
spelling	paper:paper_0166218X_v159_n16_p1699_Bonomo2023-06-08T15:15:30Z Partial characterizations of circle graphs Bonomo, Flavia Durán, Guillermo A. Grippo, Luciano Norberto Safe, Martín Darío 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. 2011 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v159_n16_p1699_Bonomo 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, Flavia Durán, Guillermo A. Grippo, Luciano Norberto Safe, Martín Darío 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.
author	Bonomo, Flavia Durán, Guillermo A. Grippo, Luciano Norberto Safe, Martín Darío
author_facet	Bonomo, Flavia Durán, Guillermo A. Grippo, Luciano Norberto Safe, Martín Darío
author_sort	Bonomo, Flavia
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
publishDate	2011
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v159_n16_p1699_Bonomo http://hdl.handle.net/20.500.12110/paper_0166218X_v159_n16_p1699_Bonomo
work_keys_str_mv	AT bonomoflavia partialcharacterizationsofcirclegraphs AT duranguillermoa partialcharacterizationsofcirclegraphs AT grippolucianonorberto partialcharacterizationsofcirclegraphs AT safemartindario partialcharacterizationsofcirclegraphs
_version_	1768544473006997504

Partial characterizations of circle graphs

Ejemplares similares