Résumé de rapport du LIF

Téléchargement / Download : pdf 196k , ps.gz 180k , bibtex

Abstract

In this paper we show that, if G is a Berge graph such that neither G nor its complement contains certain induced subgraphs, named proper wheels and long prisms, then either G is a basic perfect graph (a bipartite graph, a line graph of a bipartite graph or the complement of such graphs) or it has a skew partition that cannot occur in a minimally imperfect graph. This structural result implies that G is perfect.

Keywords

Perfect graph, decomposition.

Résumé

Dans cet article, nous démontrons que, si G est un graphe de Berge tel que ni G ni son complement ne contiennent certains sous-graphes induits, que l'on appelle roues propres et prismes longs, alors ou bien G est un graphe parfait de base (un graphe biparti, un graphe de ligne de graphe biparti, ou le complement de tels graphes) ou bien G a une partition antisymétrique qui ne peut pas exister dans un graphe minimalement imparfait. Ce résultat structurel implique que G est parfait.

Mots clés

Graphe parfait, décomposition.

Bibtex

@TECHREPORT{19-2004,
    AUTHOR	= {Michele Conforti, Gérard Cornuéjols and Giacomo Zambelli},
    TITLE	= {{Decomposing Berge graphs containing no proper wheel, long prism or their complements}},
    INSTITUTION	= {{LIF}},
    ADDRESS	= {Marseille, France},
    TYPE	= {Research report},
    NUMBER	= {19-2004},
    MONTH	= {January},
    YEAR	= {2004},
    NOTE	= {http://pageperso.lif.univ-mrs.fr/~edouard.thiel/RESP/Rapports/19-2004.html},
}