Mostrar el registro sencillo del ítem

Triangle-Free Strongly Circular-Perfect Graphs

hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorCOULONGES, Sylvain
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:04Z
dc.date.available2024-04-04T02:48:04Z
dc.date.issued2009
dc.identifier.issn0012-365X
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/191703
dc.description.abstractEnZhu introduced circular-perfect graphs as a superclass of the well-known perfect graphs and as an important χ-bound class of graphs with the smallest non-trivial χ-binding function χ(G)≤ω(G)+1. Perfect graphs have been recently characterized as those graphs without odd holes and odd antiholes as induced subgraphs [M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas, The strong perfect graph theorem, Ann. Math. (in press)]; in particular, perfect graphs are closed under complementation [L. Lovász, Normal hypergraphs and the weak perfect graph conjecture, Discrete Math. 2 (1972) 253–267]. To the contrary, circular-perfect graphs are not closed under complementation and the list of forbidden subgraphs is unknown. We study strongly circular-perfect graphs: a circular-perfect graph is strongly circular-perfect if its complement is circular perfect as well. This subclass entails perfect graphs, odd holes, and odd antiholes. As the main result, we fully characterize the triangle-free strongly circular-perfect graphs, and prove that, for this graph class, both the stable set problem and the recognition problem can be solved in polynomial time. Moreover, we address the characterization of strongly circular-perfect graphs by means of forbidden subgraphs. Results from suggest that formulating a corresponding conjecture for circular-perfect graphs is difficult; it is even unknown which triangle-free graphs are minimal circular-imperfect. We present the complete list of all triangle-free minimal not strongly circular-perfect graphs.
dc.language.isoen
dc.publisherElsevier
dc.title.enTriangle-Free Strongly Circular-Perfect Graphs
dc.typeArticle de revue
dc.subject.halInformatique [cs]/Autre [cs.OH]
bordeaux.journalDiscrete Mathematics
bordeaux.page3632-3643
bordeaux.volume309
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-00308145
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00308145v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Discrete%20Mathematics&rft.date=2009&rft.volume=309&rft.spage=3632-3643&rft.epage=3632-3643&rft.eissn=0012-365X&rft.issn=0012-365X&rft.au=COULONGES,%20Sylvain&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