This HTML5 document contains 31 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
wikipedia-huhttp://hu.wikipedia.org/wiki/
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-huhttp://hu.dbpedia.org/resource/
prop-huhttp://hu.dbpedia.org/property/
n13https://web.archive.org/web/20120205194647/http:/ginger.indstate.edu/ge/Graphs/CYCLES/
n14http://abel.math.umu.se/~klasm/Uppsatser/
n11http://www.math.uiuc.edu/~west/openp/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n6http://www.combinatorics.org/ojs/index.php/eljc/article/view/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n8http://hu.dbpedia.org/resource/Sablon:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
n4http://hu.dbpedia.org/resource/Kategória:

Statements

Subject Item
dbpedia-hu:Erdős–Gyárfás-sejtés
rdfs:label
Erdős–Gyárfás-sejtés
dct:subject
n4:Gráfelmélet n4:Sejtések n4:Erdős_Pál
dbo:wikiPageID
1458144
dbo:wikiPageRevisionID
21485332
dbo:wikiPageExternalLink
n6:v20i2p7 n11:2powcyc.html n13:index.html n14:cycex.pdf n11:index.html
prop-hu:wikiPageUsesTemplate
n8:Jegyzetek n8:Citation n8:Megoldatlan n8:Fordítás n8:Harv n8:Gráf_infobox
prop-hu:kép
Markström-Graph.svg
prop-hu:képaláírás
Markström az Erdős–Gyárfás-sejtés ellenpéldáinak számítógépes keresése során talált, 24 csúcsú, 3-reguláris síkbarajzolható gráfja, ami nem tartalmaz 4, illetve 8 hosszúságú köröket. A sejtést nem cáfolja, mivel 16 hosszúságú köröket viszont tartalmaz.
prop-hu:név
Markström-gráf
prop-hu:sugár
5
prop-hu:átmérő
6
prop-hu:csúcsok
24
prop-hu:élek
36
prop-hu:automorfizmusok
3
prop-hu:derékbőség
3
dbo:abstract
A matematika, azon belül a gráfelmélet területén az Erdős–Gyárfás-sejtés az 1995-ben Erdős Pál és Gyárfás András által megfogalmazott, bizonyítatlan állítás, mely szerint minden, legalább 3 minimális fokszámú gráf tartalmaz hosszúságú egyszerű kört. Erdős 100 dollárt ajánlott a sejtés bizonyításáért, 50 dollárt egy ellenpéldáért; a sejtés Erdős számos sejtésének egyike. Ha a sejtés hamis, az ellenpéldának olyan gráfnak kell lennie, melynek minimális fokszáma 3, és nem tartalmaz kettőhatvány hosszúságú kört. és Klas Markström számítógépes kereséseiből tudjuk, hogy bármely ellenpéldának legalább 17 csúcsból kell állnia, egy 3-reguláris gráf esetén pedig legalább 30 csúcsból. Markström talál négy olyan, 24 csúcsú gráfot, melyben kizárólag 16 hosszú kettőhatvány-körök voltak. A négy gráf egyike síkbarajzolható; az Erdős–Gyárfás-sejtést azonban a 3-szorosan összefüggő, 3-reguláris síkbarajzolható gráfok esetére már sikerült belátni. Születtek gyengébb eredmények, melyek a gráf fokszámát és az elkerülhetetlen körhosszúságokat kapcsolják össze: létezik hosszúságok olyan S halmaza, ahol |S| = O(n0,99), hogy minden 10 vagy magasabb átlagos fokszámú gráf tartalmaz S-ben lévő hosszúságú kört ; pedig felső korlátot ad a kettőhatvány hosszúságú kört nem tartalmazó, n csúcsú gráfok átlagos fokszámára: , ahol log* a bináris jelenti. A sejtést igazolta síkbarajzolható karommentes gráfokra, pedig olyan gráfokra, melyek nem tartalmaznak nagyméretű feszített csillagokat és néhány más, fokszámra vonatkozó követelménynek eleget tesznek.
prov:wasDerivedFrom
wikipedia-hu:Erdős–Gyárfás-sejtés?oldid=21485332&ns=0
dbo:wikiPageLength
5242
foaf:isPrimaryTopicOf
wikipedia-hu:Erdős–Gyárfás-sejtés
Subject Item
wikipedia-hu:Erdős–Gyárfás-sejtés
foaf:primaryTopic
dbpedia-hu:Erdős–Gyárfás-sejtés