On classes of minimal circular-imperfect graphs
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| dc.contributor.author | PECHER, Arnaud | |
| hal.structure.identifier | Institute for Mathematical Optimization [IMO] | |
| dc.contributor.author | WAGLER, Annegret K. | |
| dc.date.accessioned | 2024-04-04T02:48:12Z | |
| dc.date.available | 2024-04-04T02:48:12Z | |
| dc.date.issued | 2008 | |
| dc.identifier.issn | 0166-218X | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/191718 | |
| dc.description.abstractEn | Circular-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.iso | en | |
| dc.publisher | Elsevier | |
| dc.title.en | On classes of minimal circular-imperfect graphs | |
| dc.type | Article de revue | |
| dc.subject.hal | Informatique [cs]/Autre [cs.OH] | |
| bordeaux.journal | Discrete Applied Mathematics | |
| bordeaux.page | 998--1010 | |
| bordeaux.volume | 156 | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-00307755 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00307755v1 | |
| bordeaux.COinS | ctx_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 |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||