Claw-free circular-perfect graphs
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| hal.structure.identifier | Algorithmes Parallèles et Optimisation [IRIT-APO] | |
| dc.contributor.author | PÊCHER, Arnaud | |
| hal.structure.identifier | Department of Applied Mathematics [Kaohsiung] | |
| dc.contributor.author | ZHU, Xuding | |
| dc.date.accessioned | 2024-04-04T02:32:22Z | |
| dc.date.available | 2024-04-04T02:32:22Z | |
| dc.date.created | 2009 | |
| dc.date.issued | 2010 | |
| dc.identifier.issn | 0364-9024 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/190379 | |
| dc.description.abstractEn | The circular chromatic number of a graph is a well-studied refinement of the chromatic number. Circular-perfect graphs form a superclass of perfect graphs defined by means of this more general coloring concept. This paper studies claw-free circular-perfect graphs. First we prove that if $G$ is a connected claw-free circular-perfect graph with $\chi(G) > \omega(G)$, then $\min\{\alpha(G), \omega(G)\} =2$. We use this result to design a polynomial time algorithm that computes the circular chromatic number of claw-free circular-perfect graphs. A consequence of the strong perfect graph theorem is that minimal imperfect graphs $G$ have $\min \{\alpha(G), \omega(G)\} = 2$. In contrast to this result, it is shown in \cite{PanZhu2006} that minimal circular-imperfect graphs $G$ can have arbitrarily large independence number and arbitrarily large clique number. In this paper, we prove that claw-free minimal circular-imperfect graphs $G$ have $\min \{\alpha(G), \omega(G)\} \leq 3$. | |
| dc.description.sponsorship | / - ANR-09-BLAN-0373 | |
| dc.language.iso | en | |
| dc.publisher | Wiley | |
| dc.title.en | Claw-free circular-perfect graphs | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.1002/jgt.20474 | |
| dc.subject.hal | Sciences de l'Homme et Société/Sciences de l'information et de la communication | |
| dc.subject.hal | Informatique [cs] | |
| bordeaux.journal | Journal of Graph Theory | |
| bordeaux.page | 163-172 | |
| bordeaux.volume | 65 | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.issue | 2 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-00431241 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00431241v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Journal%20of%20Graph%20Theory&rft.date=2010&rft.volume=65&rft.issue=2&rft.spage=163-172&rft.epage=163-172&rft.eissn=0364-9024&rft.issn=0364-9024&rft.au=P%C3%8ACHER,%20Arnaud&ZHU,%20Xuding&rft.genre=article |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||