| dbo:abstract
|
- 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 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. La conjecture a été démontrée par Jérémie Chalopin et Daniel Gonçalves en 2009. (fr)
- In mathematics, Scheinerman's conjecture, now a theorem, states that every planar graph is the intersection graph of a set of line segments in the plane. This conjecture was formulated by E. R. Scheinerman in his Ph.D. thesis , following earlier results that every planar graph could be represented as the intersection graph of a set of simple curves in the plane. It was proven by Jeremie Chalopin and Daniel Gonçalves. For instance, the graph G shown below to the left may be represented as the intersection graph of the set of segments shown below to the right. Here, vertices of G are represented by straight line segments and edges of G are represented by intersection points. Scheinerman also conjectured that segments with only three directions would be sufficient to represent 3-colorable graphs, and conjectured that analogously every planar graph could be represented using four directions. If a graph is represented with segments having only k directionsand no two segments belong to the same line, then the graph can be colored using k colors, one color for each direction. Therefore, if every planar graph can be represented in this way with only four directions,then the four color theorem follows. and proved that every bipartite planar graph can be represented as an intersection graph of horizontal and vertical line segments; for this result see also . proved that every triangle-free planar graph can be represented as an intersection graph of line segments having only three directions; this result implies Grötzsch's theorem that triangle-free planar graphs can be colored with three colors. proved that if a planar graph G can be 4-colored in such a way that no separating cycle uses all four colors, then G has a representation as an intersection graph of segments. proved that planar graphs are in 1-STRING, the class of intersection graphs of simple curves in the plane that intersect each other in at most one crossing point per pair. This class is intermediate between the intersection graphs of segments appearing in Scheinerman's conjecture and the intersection graphs of unrestricted simple curves from the result of Ehrlich et al. It can also be viewed as a generalization of the circle packing theorem, which shows the same result when curves are allowed to intersect in a tangent. The proof of the conjecture by was based on an improvement of this result. (en)
- Гипотеза Шейнермана, теперь доказанная теорема, утверждает, что любой планарный граф является графом пересечений набора отрезков на плоскости. Эту гипотезу сформулировал в своей кандидатской диссертации, следуя более раннему результату, что любой планарный граф можно представить как граф пересечений простых кривых на плоскости. Теорему доказали Чалопин и Гонсалвис. (ru)
- Гіпо́теза Шейнермана, тепер доведена теорема, стверджує, що будь-який планарний граф є графом перетинів набору відрізків на площині. Цю гіпотезу сформулював у своїй кандидатській дисертації, спираючись на раніший результат, що будь-який планарний граф можна подати як граф перетинів простих кривих на площині. Теорему довели Чалопін і Гонсалвіс. (uk)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 7266 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:first
| |
| dbp:last
|
- Gonçalves (en)
- Chalopin (en)
|
| dbp:wikiPageUsesTemplate
| |
| dbp:year
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- 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 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. La conjecture a été démontrée par Jérémie Chalopin et Daniel Gonçalves en 2009. (fr)
- Гипотеза Шейнермана, теперь доказанная теорема, утверждает, что любой планарный граф является графом пересечений набора отрезков на плоскости. Эту гипотезу сформулировал в своей кандидатской диссертации, следуя более раннему результату, что любой планарный граф можно представить как граф пересечений простых кривых на плоскости. Теорему доказали Чалопин и Гонсалвис. (ru)
- Гіпо́теза Шейнермана, тепер доведена теорема, стверджує, що будь-який планарний граф є графом перетинів набору відрізків на площині. Цю гіпотезу сформулював у своїй кандидатській дисертації, спираючись на раніший результат, що будь-який планарний граф можна подати як граф перетинів простих кривих на площині. Теорему довели Чалопін і Гонсалвіс. (uk)
- In mathematics, Scheinerman's conjecture, now a theorem, states that every planar graph is the intersection graph of a set of line segments in the plane. This conjecture was formulated by E. R. Scheinerman in his Ph.D. thesis , following earlier results that every planar graph could be represented as the intersection graph of a set of simple curves in the plane. It was proven by Jeremie Chalopin and Daniel Gonçalves. (en)
|
| rdfs:label
|
- Conjecture de Scheinerman (fr)
- Scheinerman's conjecture (en)
- Гипотеза Шейнермана (ru)
- Гіпотеза Шейнермана (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
