This HTML5 document contains 15 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/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n12http://www.openproblemgarden.org/op/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n6http://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:Gyárfás–Sumner-sejtés
rdfs:label
Gyárfás–Sumner-sejtés
dct:subject
n4:Sejtések n4:Gráfok_színezése
dbo:wikiPageID
1592910
dbo:wikiPageRevisionID
20694411
dbo:wikiPageExternalLink
n12:graphs_with_a_forbidden_induced_tree_are_chi_bounded
prop-hu:wikiPageUsesTemplate
n6:Fordítás n6:Reflist n6:R n6:Megoldatlan
dbo:abstract
A matematika, azon belül a gráfelmélet területén a Gyárfás–Sumner-sejtés azt állítja, hogy tetszőleges fát és teljes gráfot választva, a feszített részgráfként sem -t, sem -t nem tartalmazó gráfok konstans számú színnel jól színezhetők. Ezzel ekvivalens megfogalmazás szerint, a - és -mentes gráfok .A sejtés nevét Gyárfás Andrásról és kapta, akik egymástól függetlenül 1975-ben, illetve 1981-ben megfogalmazták. Jelenleg bizonyítatlan. A sejtésben nem lehetséges -t kört tartalmazó gráfra cserélni. Ahogy Erdős Pál és Hajnal András megmutatták, léteznek tetszőlegesen magas kromatikus számú, ugyanakkor tetszőlegesen nagy girthű háromszögmentes gráfok. Ezen gráfok felhasználásával előállíthatók olyan gráfok, amik elkerülnek bármely fixen választott, kört tartalmazó gráfot és (2 csúcsnál nagyobb) klikket feszített részgráfként, de tetszőlegesen választott értéknél magasabb a kromatikus számuk. A sejtést bizonyították néhány speciálisan megválasztott -re, így útgráfokra, csillagokra és kettő sugarú fákra.Ismert az is, hogy azok a gráfok, melyek nem tartalmaznak bármely konkrét fát felosztásként, -korlátosak.
prov:wasDerivedFrom
wikipedia-hu:Gyárfás–Sumner-sejtés?oldid=20694411&ns=0
dbo:wikiPageLength
4647
foaf:isPrimaryTopicOf
wikipedia-hu:Gyárfás–Sumner-sejtés
Subject Item
wikipedia-hu:Gyárfás–Sumner-sejtés
foaf:primaryTopic
dbpedia-hu:Gyárfás–Sumner-sejtés