Une étude des graphes jumeaux via l'auto-abritement

Abstract

On étudie la conjecture des graphes jumeaux dénombrables, cas spécifique d’une conjecture de Thomassé, qui dit que le nombre de jumeaux d’un graphe dénombrable ( ses sous-graphes propres desquels il est aussi un sous-graphe propre) est soit nul, soit infini. On commence par étudier les graphes auto-abrités, que nous définissons, et en utilisant notre classification de ces graphes nous prouvons la conjecture dans certains cas, en précisant la cardinalité exacte du nombre de jumeaux. Nous donnons également des contre-exemples à l’article de l’arXiv «Self-contained graphs».

We make progress on the Graph Alternative Conjecture, a special case of a conjecture of Thomassé which says that the number of twins of a countable graph (i.e. its proper subgraphs of which that graph is also a proper subgraph) is either null or infinite. We begin by studying self-embedded graphs, which we define, and using our classification of these graphs, we prove the conjecture in some cases while specifying the exact number of twins. We also give counter-examples to a paper on arXiv called "Self-contained graphs".