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: 2008
Materias:
circular-arc graphs
claw-free chordal
cographs
diamond-free graphs
paw-free graphs
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v30_nC_p45_Bonomo
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 paper:paper_15710653_v30_nC_p45_Bonomo
record_format dspace
spelling paper:paper_15710653_v30_nC_p45_Bonomo2023-06-08T16:24:23Z 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 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. 2008 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v30_nC_p45_Bonomo 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, 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
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.
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 2008
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v30_nC_p45_Bonomo
http://hdl.handle.net/20.500.12110/paper_15710653_v30_nC_p45_Bonomo
work_keys_str_mv AT bonomoflavia partialcharacterizationsofcirculararcgraphs
AT duranguillermoa partialcharacterizationsofcirculararcgraphs
AT grippolucianonorberto partialcharacterizationsofcirculararcgraphs
AT safemartindario partialcharacterizationsofcirculararcgraphs
_version_ 1768544383986040832

Ejemplares similares