Résumé de rapport du LIF

Téléchargement / Download : pdf 104k , ps.gz 136k , bibtex

Abstract

In this note, a constructive proof is given that the classes of proper interval graphs and unit interval graphs coincide, a result originally established by F.S. Roberts.

Keywords

Proper interval graphs, unit interval graphs, characterizations, constructive proof.

Résumé

Dans cette note, nous donnons une preuve constructive d'un résultat de F.S. Roberts qui établit que les classe des graphes d'intervalles propres et des graphes d'intervalles unitaires coïncident.

Mots clés

Graphes d'intervalles propres, graphes d'intervalles unitaires, caractérisations, preuve constructive.

Bibtex

@TECHREPORT{11-2003,
    AUTHOR	= {Frédéric Gardi},
    TITLE	= {{A note on the Roberts characterization of proper and unit interval graphs}},
    INSTITUTION	= {{LIF}},
    ADDRESS	= {Marseille, France},
    TYPE	= {Research report},
    NUMBER	= {11-2003},
    MONTH	= {January},
    YEAR	= {2003},
    NOTE	= {http://pageperso.lif.univ-mrs.fr/~edouard.thiel/RESP/Rapports/11-2003.html},
}