Show item record

dc.contributor.advisorRosenberg, Ivo G.
dc.contributor.authorChampagne-Paradis, Audrey
dc.date.accessioned2011-09-16T15:25:07Z
dc.date.availableNO_RESTRICTIONen
dc.date.available2011-09-16T15:25:07Z
dc.date.issued2011-07-07
dc.date.submitted2011-05
dc.identifier.urihttp://hdl.handle.net/1866/5288
dc.subjectThéorie des graphesen
dc.subjectGraph theoryen
dc.subjectDétouren
dc.subjectDetouren
dc.subjectCheminen
dc.subjectPathen
dc.subjectPlus long cheminen
dc.subjectLongest pathen
dc.subjectPartitionen
dc.subject.otherMathematics / Mathématiques (UMI : 0405)en
dc.titleLa conjecture de partitionnement des cheminsen
dc.typeThèse ou mémoire / Thesis or Dissertation
etd.degree.disciplineMathématiquesen
etd.degree.grantorUniversité de Montréalfr
etd.degree.levelMaîtrise / Master'sen
etd.degree.nameM. Sc.en
dcterms.abstractSoit G = (V, E) un graphe simple fini. Soit (a, b) un couple d’entiers positifs. On note par τ(G) le nombre de sommets d’un chemin d’ordre maximum dans G. Une partition (A,B) de V(G) est une (a,b)−partition si τ(⟨A⟩) ≤ a et τ(⟨B⟩) ≤ b. Si G possède une (a, b)−partition pour tout couple d’entiers positifs satisfaisant τ(G) = a+b, on dit que G est τ−partitionnable. La conjecture de partitionnement des chemins, connue sous le nom anglais de Path Partition Conjecture, cherche à établir que tout graphe est τ−partitionnable. Elle a été énoncée par Lovász et Mihók en 1981 et depuis, de nombreux chercheurs ont tenté de démontrer cette conjecture et plusieurs y sont parvenus pour certaines classes de graphes. Le présent mémoire rend compte du statut de la conjecture, en ce qui concerne les graphes non-orientés et ceux orientés.en
dcterms.abstractLet G = (V,E) be a finite simple graph. We denote the number of vertices in a longest path in G by τ(G). A partition (A,B) of V is called an (a,b)−partition if τ(⟨A⟩) ≤ a and τ(⟨B⟩) ≤ b. If G can be (a,b)−partitioned for every pair of positive integers (a, b) satisfying a + b = τ (G), we say that G is τ −partitionable. The following conjecture, called The Path Partition Conjecture, has been stated by Lovász and Mihók in 1981 : every graph is τ−partitionable. Since that, many researchers prove that this conjecture is true for several classes of graphs and digraphs. This study summarizes the different results about the Path Partition conjecture.en
dcterms.languagefraen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show item record