Abstract FR:

Ce travail aborde dans trois parties trois problemes de la theorie des graphes. Dans la premiere partie, cycles hamiltoniens et graphes planaires, nous developpons une procedure de construction de certaines familles de graphes planaires 3-connexes, hamiltoniens et non hamiltoniens. Ces graphes echappent aux caracterisations donnees par les theoremes de tutte et whitney d'une part (conditions suffisantes) et par le theoreme de grinberg d'autre part (conditions necessaires). Cette procedure s'avere utile pour la production d'exemples de graphes en vue de tester des heuristiques pour trouver des chemins hamiltoniens, ce qui est un probleme np-complet. Dans la deuxieme partie, generalisations du delta-sous-graphe pour les multigraphes, nous nous proposons d'etendre aux multigraphes des concepts deja utilises pour les colorations d'aretes d'un graphe simple. Dans la troisieme partie, pavages de figures par des dominos, nous developpons une procedure d'obtention systematique de tous les pavages d'une figure pavable, en mettant en evidence la structure de treillis formee par l'ensemble de ces pavages. Pour cela, nous commencons par exposer, dans le chapitre 7, des resultats specifiques obtenus a partir de la presentation par thurston, en 1990, d'un algorithme lineaire pour la pavage d'une figure plane par dominos, qui utilise l'approche de la theorie des groupes. Nous privilegions, cependant, l'approche de fournier, dont l'etude de l'algorithme de thurston met en evidence le rapport entre la pavabilite d'une figure et la condition de hall pour les couplages