• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Graphes parfais et paires d'amis

Linhares Sales, Claudia 18 January 1996 (has links) (PDF)
A partir du concept de paire d'amis dans un graphe (paire de sommets telle que toutes les chaînes sans cordes qui les relient sont de longueur paire) deux classes de graphes parfaits ont été déjà définies. La première notée QPS (graphes de quasi-parité stricte) est définie par l'existence de paires d'amis pour tout sous-graphe induit incomplet. La deuxième notée PC (graphes parfaitement contractibles) est définie à partir de l'idée algorithmique de coloration du graphe ou de ses sous-graphes induits par enchaînement de contractions successives des sommets d'une paire d'amis jusqu'à obtenir une clique, auquel cas la coloration est optimale. Dans cette thèse nous avons abordé deux conjectures: la première (relative à la classe QPS) énoncée par S. Hougardy est proche de la conjecture forte de graphes parfaits et la deuxième énoncée par H. Everett et B. Reed consite à caractériser les graphes PC par sous-graphes exclus. Nous avons pu valider ces deux conjectures dans deux cas: le cas des graphes planaires et le cas des graphes sans griffe. Ces quatre résultats sont assortis d'algorithmes polynomiaux de reconnaissance (ainsi que de coloration pour la classe PC)

Page generated in 0.0716 seconds