Mostrar el registro sencillo del ítem

On classes of minimal circular-imperfect graphs

hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorPECHER, Arnaud
hal.structure.identifierInstitute for Mathematical Optimization [IMO]
dc.contributor.authorWAGLER, Annegret K.
dc.date.accessioned2024-04-04T02:48:12Z
dc.date.available2024-04-04T02:48:12Z
dc.date.issued2008
dc.identifier.issn0166-218X
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/191718
dc.description.abstractEnCircular-perfect graphs form a natural superclass of perfect graphs: on the one hand due to their definition by means of a more general coloring concept, on the other hand as an important class of \chi-bound graphs with the smallest non-trivial \chi-binding function \chi(G) ≤ \omega(G) + 1. The Strong Perfect Graph Conjecture, recently settled by Chudnovsky et al. [4], provides a characterization of perfect graphs by means of forbidden subgraphs. It is, therefore, natural to ask for an analogous conjecture for circular-perfect graphs, that is for a characterization of all minimal circular-imperfect graphs. At present, not many minimal circular-imperfect graphs are known. This paper studies the circular-(im)perfection of some families of graphs: normalized circular cliques, partitionable graphs, planar graphs, and complete joins. We thereby exhibit classes of minimal circular-imperfect graphs, namely, certain partitionable webs, a subclass of planar graphs, and odd wheels and odd antiwheels. As those classes appear to be very different from a structural point of view, we infer that formulating an appropriate conjecture for circular-perfect graphs, as analogue to the Strong Perfect Graph Theorem, seems to be difficult.
dc.language.isoen
dc.publisherElsevier
dc.title.enOn classes of minimal circular-imperfect graphs
dc.typeArticle de revue
dc.subject.halInformatique [cs]/Autre [cs.OH]
bordeaux.journalDiscrete Applied Mathematics
bordeaux.page998--1010
bordeaux.volume156
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-00307755
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00307755v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Discrete%20Applied%20Mathematics&rft.date=2008&rft.volume=156&rft.spage=998--1010&rft.epage=998--1010&rft.eissn=0166-218X&rft.issn=0166-218X&rft.au=PECHER,%20Arnaud&WAGLER,%20Annegret%20K.&rft.genre=article


Archivos en el ítem

ArchivosTamañoFormatoVer

No hay archivos asociados a este ítem.

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem