Partial characterizations of circular-arc graphs

Mostrar todas las versiones(2)

A circular-arc graph is the intersection graph of a family of arcs on a circle. A characterization by forbidden induced subgraphs for this class of graphs is not known, and in this work we present a partial result in this direction. We characterize circular-arc graphs by a list of minimal forbidden...

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:	2009
Materias:	Circular-arc graphs Claw-free chordal graphs Cographs Diamond-free graphs Paw-free graphs Chordal graphs Circular-arc graph Claw-free Forbidden induced subgraphs Free graphs Intersection graph Partial characterization Characterization Diamonds Cavity resonators
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03649024_v61_n4_p289_Bonomo http://hdl.handle.net/20.500.12110/paper_03649024_v61_n4_p289_Bonomo
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_03649024_v61_n4_p289_Bonomo
record_format	dspace
spelling	paper:paper_03649024_v61_n4_p289_Bonomo2023-06-08T15:35:37Z Partial characterizations of circular-arc graphs Bonomo, Flavia Durán, Guillermo A. Grippo, Luciano Norberto Safe, Martín Darío Circular-arc graphs Claw-free chordal graphs Cographs Diamond-free graphs Paw-free graphs Chordal graphs Circular-arc graph Circular-arc graphs Claw-free Claw-free chordal graphs Cographs Forbidden induced subgraphs Free graphs Intersection graph Partial characterization Paw-free graphs Characterization Diamonds Cavity resonators A circular-arc graph is the intersection graph of a family of arcs on a circle. A characterization by forbidden induced subgraphs for this class of graphs is not known, and in this work we present a partial result in this direction. We characterize circular-arc graphs by a list of minimal forbidden induced subgraphswhen the graph belongs to any of the following classes: P 4-free graphs, paw-free graphs, claw-free chordal graphs and diamond-free graphs. © 2009 Wiley Periodicals, Inc. 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. 2009 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03649024_v61_n4_p289_Bonomo http://hdl.handle.net/20.500.12110/paper_03649024_v61_n4_p289_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	Circular-arc graphs Claw-free chordal graphs Cographs Diamond-free graphs Paw-free graphs Chordal graphs Circular-arc graph Circular-arc graphs Claw-free Claw-free chordal graphs Cographs Forbidden induced subgraphs Free graphs Intersection graph Partial characterization Paw-free graphs Characterization Diamonds Cavity resonators
spellingShingle	Circular-arc graphs Claw-free chordal graphs Cographs Diamond-free graphs Paw-free graphs Chordal graphs Circular-arc graph Circular-arc graphs Claw-free Claw-free chordal graphs Cographs Forbidden induced subgraphs Free graphs Intersection graph Partial characterization Paw-free graphs Characterization Diamonds Cavity resonators Bonomo, Flavia Durán, Guillermo A. Grippo, Luciano Norberto Safe, Martín Darío Partial characterizations of circular-arc graphs
topic_facet	Circular-arc graphs Claw-free chordal graphs Cographs Diamond-free graphs Paw-free graphs Chordal graphs Circular-arc graph Circular-arc graphs Claw-free Claw-free chordal graphs Cographs Forbidden induced subgraphs Free graphs Intersection graph Partial characterization Paw-free graphs Characterization Diamonds Cavity resonators
description	A circular-arc graph is the intersection graph of a family of arcs on a circle. A characterization by forbidden induced subgraphs for this class of graphs is not known, and in this work we present a partial result in this direction. We characterize circular-arc graphs by a list of minimal forbidden induced subgraphswhen the graph belongs to any of the following classes: P 4-free graphs, paw-free graphs, claw-free chordal graphs and diamond-free graphs. © 2009 Wiley Periodicals, Inc.
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 circular-arc graphs
title_short	Partial characterizations of circular-arc graphs
title_full	Partial characterizations of circular-arc graphs
title_fullStr	Partial characterizations of circular-arc graphs
title_full_unstemmed	Partial characterizations of circular-arc graphs
title_sort	partial characterizations of circular-arc graphs
publishDate	2009
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03649024_v61_n4_p289_Bonomo http://hdl.handle.net/20.500.12110/paper_03649024_v61_n4_p289_Bonomo
work_keys_str_mv	AT bonomoflavia partialcharacterizationsofcirculararcgraphs AT duranguillermoa partialcharacterizationsofcirculararcgraphs AT grippolucianonorberto partialcharacterizationsofcirculararcgraphs AT safemartindario partialcharacterizationsofcirculararcgraphs
_version_	1768544597684781056

Partial characterizations of circular-arc graphs

Ejemplares similares