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

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

Namespace Prefixes

PrefixIRI
n10http://www.dtic.mil/dtic/tr/fulltext/u2/
wikipedia-huhttp://hu.wikipedia.org/wiki/
dcthttp://purl.org/dc/terms/
n13https://ir.library.louisville.edu/etd/815/
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#
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n12http://hu.dbpedia.org/resource/Sablon:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
n6http://hu.dbpedia.org/resource/Kategória:

Statements

Subject Item
dbpedia-hu:Totális_színezés
rdfs:label
Totális színezés
dct:subject
n6:Gráfok_színezése
dbo:wikiPageID
1542536
dbo:wikiPageRevisionID
20880452
dbo:wikiPageExternalLink
n10:705364.pdf%7Ccontribution=8. n13:
prop-hu:wikiPageUsesTemplate
n12:ISBN n12:Jegyzetek n12:Cite_journal n12:Doi n12:Citation n12:Fordítás
dbo:abstract
A matematika, azon belül a gráfelmélet területén egy gráf totális színezése (total coloring) a gráfszínezések olyan fajtája, amikor a gráf csúcsai és élei is színt kapnak. Ha külön nem jelölik, mindig a gráf „jó” totális színezéséről van szó, tehát sem érintkező élek, sem valamely él végpontjai nem lehetnek azonos színűek. Egy G gráf χ″(G) totális kromatikus száma a G totális színezéséhez szükséges legkevesebb szín száma. A totális színezés a gráfot particionálja. Egy G gráfhoz tartozó T = T(G) totális gráf az a gráf, melynek (i) csúcshalmaza megfelel G csúcsainak és éleinek (ii) két csúcs pontosan akkor szomszédos T-ben, ha a nekik megfelelő elemek szomszédosak vagy illeszkednek G-ben. (A totális gráf megkapható úgy is, ha G minden élét felbontjuk, majd a felbontott gráfot második hatványra emeljük.) A totális színezés megegyezik a totális gráf jó színezésével. χ″(G) néhány tulajdonsága: 1. * χ″(G) ≥ Δ(G) + 1. 2. * χ″(G) ≤ Δ(G) + 1026. (Molloy, Reed 1998) 3. * χ″(G) ≤ Δ(G) + 8 ln8(Δ(G)) elegendően nagy Δ(G)-re. (Hind, Molloy, Reed 1998) 4. * χ″(G) ≤ ch′(G) + 2. Δ(G) a maximális fokszám, ch′(G) pedig a lista-élkromatikus szám. A totális színezés természetes módon adja magát a csúcs- és élszínezések egyesítéséből. A következő logikus lépés a Brooks- vagy Vizing-típusú felső korlátok keresése a totális kromatikus számra a maximális fokszám függvényében. Mint kiderült, ez utóbbi probléma olyan nehéz, hogy több mint 40 éve nem boldogulnak vele a matematikusok. Triviálisan belátható, hogy a totális kromatikus szám nem lehet kisebb a maximális fokszám + 1, azaz Δ(G) + 1-nél (ezeket Class 1 gráfnak nevezik), néhány gráftípus esetében pedig (mint a hárommal nem osztható hosszúságú körök, és a alakú teljes páros gráfok) Δ(G) + 2 színre van szükség. Nem sikerült azonban olyan gráfra bukkanni, ahol a Δ(G) + 2 szín ne lenne elegendő. Ezért a következő sejtést állították fel, mely szerint csak az említett két gráfosztály létezik a totális színezés szempontjából: Totális színezési sejtés
prov:wasDerivedFrom
wikipedia-hu:Totális_színezés?oldid=20880452&ns=0
dbo:wikiPageLength
5683
foaf:isPrimaryTopicOf
wikipedia-hu:Totális_színezés
Subject Item
dbpedia-hu:Totális_gráf
dbo:wikiPageRedirects
dbpedia-hu:Totális_színezés
Subject Item
dbpedia-hu:Totális_kromatikus_szám
dbo:wikiPageRedirects
dbpedia-hu:Totális_színezés
Subject Item
wikipedia-hu:Totális_színezés
foaf:primaryTopic
dbpedia-hu:Totális_színezés