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, F., Durán, G., Grippo, L.N., Safe, M.D.
Formato:	JOUR
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:	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	todo:paper_03649024_v61_n4_p289_Bonomo
record_format	dspace
spelling	todo:paper_03649024_v61_n4_p289_Bonomo2023-10-03T15:27:40Z Partial characterizations of circular-arc graphs Bonomo, F. Durán, G. Grippo, L.N. Safe, M.D. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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, F. Durán, G. Grippo, L.N. Safe, M.D. 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.
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 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
url	http://hdl.handle.net/20.500.12110/paper_03649024_v61_n4_p289_Bonomo
work_keys_str_mv	AT bonomof partialcharacterizationsofcirculararcgraphs AT durang partialcharacterizationsofcirculararcgraphs AT grippoln partialcharacterizationsofcirculararcgraphs AT safemd partialcharacterizationsofcirculararcgraphs
_version_	1807322346604724224

Partial characterizations of circular-arc graphs

Ejemplares similares