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
cographs
diamond-free graphs
paw-free graphs
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_15710653_v30_nC_p45_Bonomo
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_15710653_v30_nC_p45_Bonomo
record_format dspace
spelling todo:paper_15710653_v30_nC_p45_Bonomo2023-10-03T16:27:02Z Partial Characterizations of Circular-Arc Graphs Bonomo, F. Durán, G. Grippo, L.N. Safe, M.D. circular-arc graphs claw-free chordal cographs diamond-free graphs paw-free graphs 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 subgraphs when the graph belongs to the following classes: diamond-free graphs, P4-free graphs, paw-free graphs, and claw-free chordal graphs. © 2008 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_15710653_v30_nC_p45_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
cographs
diamond-free graphs
paw-free graphs
spellingShingle circular-arc graphs
claw-free chordal
cographs
diamond-free graphs
paw-free graphs
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
cographs
diamond-free graphs
paw-free graphs
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 subgraphs when the graph belongs to the following classes: diamond-free graphs, P4-free graphs, paw-free graphs, and claw-free chordal graphs. © 2008 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 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_15710653_v30_nC_p45_Bonomo
work_keys_str_mv AT bonomof partialcharacterizationsofcirculararcgraphs
AT durang partialcharacterizationsofcirculararcgraphs
AT grippoln partialcharacterizationsofcirculararcgraphs
AT safemd partialcharacterizationsofcirculararcgraphs
_version_ 1807319116594282496

Ejemplares similares