Conjecture de Scheinerman

En mathématiques, et notamment en théorie des graphes, la conjecture de Scheinerman, qui, maintenant qu'elle est démontrée, est un théorème, affirme que tout graphe planaire est le graphe d'intersection d'un ensemble de segments de droite dans le plan. Cette conjecture a été formulée par Edward R. Scheinerman dans sa thèse de doctorat[1],[2] de 1984, à la suite de résultats antérieurs selon lesquels chaque graphe planaire pouvait être représenté comme le graphe d'intersection d'un ensemble de courbes simples dans le plan de Ehrlich, Even et Tarjan[3]. La conjecture a été démontrée par Jérémie Chalopin et Daniel Gonçalves en 2009[4].

Un exemple

Le graphe G affiché ci-dessous à gauche peut être représenté comme le graphe d'intersection de l'ensemble des segments donnés ci-dessous à droite. Ici, les sommets de G sont représentés par des segments de droite et les arêtes de G sont représentées par les points d'intersection.

     

Autres conjectures et résultats

Scheinerman a également conjecturé que des segments en seulement trois directions seraient suffisants pour représenter des graphes tricolores, et West[5] a conjecturé que, de manière analogue, tout graphe planaire pouvait être représenté en utilisant quatre directions. Si un graphe est représenté par des segments en k directions et que deux segments ne sont pas sur une même droite, alors le graphe peut être coloré en utilisant k couleurs, une couleur pour chaque direction. Par conséquent, si chaque graphe planaire peut être représenté de cette manière avec seulement quatre directions, cela fournit une démonstration du théorème des quatre couleurs.

Hartman, Newman et Ziv[6] et de Fraysseix, Ossona de Mendez et Pach[7] (1991) ont montré en 1991 que tout graphe biparti planaire peut être représenté comme un graphe d'intersection de segments de droites horizontales et verticales, résultat repris par see also Czyzowicz, Kranakis et Urrutia[8]. De Castro et al[9]. (2002) ont prouvé que tout graphe sans triangle planaire peut être représenté comme le graphe d'intersection de segments de droites ayant seulement trois directions ; ce résultat implique le théorème de Grötzsch[10]qui dit qu'un graphe sans triangle peut être coloré en trois couleurs. de Fraysseix et Ossona de Mendez[11] ont prouvé que si un graphe G peut être coloré en 4 couleurs de sont qu'il n'y a pas de cycle séparateur qui utilise les quatre couleurs, alors G admet une représentation comme graphe d'intersection de segments.

Chalopin, Gonçalves et Ochem[12] ont prouvé que les graphes planaires sont dans la classe « 1-STRING », qui est la classe des graphes d'intersection de courbes simples dans le plan qui ont au plus un point d'intersection deux-à-deux. Cette classe est intermédiaire entre la classe des graphes d'intersection de segments de la conjecture de Scheinerman et les graphes d'intersection de courbes simples de Ehrlich et al.[3]. Il peut également être vu comme une généralisation du théorème des empilements de cercles (en) qui montre le même résultat lorsque les courbes peuvent se couper en une tangente. La preuve de la conjecture par Chalopin et Gonçalves[4] était basée sur une amélioration de ce résultat.

Notes et références
  1. (en) « Edward R. Scheinerman », sur le site du Mathematics Genealogy Project.
  2. Scheinerman 1984.
  3. Ehrlich, Even et Tarjan 1976
  4. Chalopin et Gonçalves 2009.
  5. West 1991.
  6. Hartman, Newman et Ziv 1991.
  7. de Fraysseix, Ossona de Mendez et Pach 1991.
  8. Czyzowicz, Kranakis et Urrutia 1998.
  9. De Castro et al. 2002.
  10. Grötzsch 1959.
  11. de Fraysseix et Ossona de Mendez 2005.
  12. Chalopin, Gonçalves et Ochem 2007.

Bibliographie
  • Daniel Gonçalves, « 3-Colorable Planar Graphs Have an Intersection Segment Representation Using 3 Slopes », Lecture Notes in Computer Science,, vol. 11789 « Graph-Theoretic Concepts in Computer Science. WG 2019 »,‎ , p. 351–363 (DOI 10.1007/978-3-030-30786-8_27, HAL lirmm-02407838).
  • Portail des mathématiques
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.