About: Graph coloring

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

Assignment of colors to elements of a graph subject to certain constraints

thumbnail
Property Value
dbo:description
  • присвоєння кольорів елементам графа з урахуванням певних обмежень (uk)
  • přiřazení barev objektům v grafu na základě definovaných omezení (cs)
  • αντιστοιχία των κόμβων ενός γραφήματος σε χρώματα ώστε να μην υπάρχουν δύο γειτονικοί κόμβοι με το ίδιο χρώμα (el)
  • caso speciale di etichettamento dei grafi (it)
  • assignment of colors to elements of a graph subject to certain constraints (en)
  • Zuordnung einer Farbe zu jedem Element eines Graphen (de)
  • przypisywanie kolorów obiektom grafu zgodnie z narzuconymi regułami (pl)
  • частный случай разметки графа (ru)
dbo:thumbnail
dbo:wikiPageExternalLink
dbo:wikiPageWikiLink
dbp:above
  • Graph coloring (en)
dbp:abovestyle
  • background: #DD9 (en)
dbp:authorLink
  • Jan Mycielski (en)
  • W. T. Tutte (en)
  • Alexander Zykov (en)
dbp:data
  • 3 (xsd:integer)
  • dbr:NP-hardness
  • dbr:♯P-complete
  • dbr:NP-completeness
  • O (en)
  • GT4 (en)
  • Chromatic number (en)
  • Chromatic polynomial (en)
  • χ (en)
  • Does G admit a proper vertex coloring with k colors? (en)
  • FPRAS for restricted cases (en)
  • Graph G with n vertices. (en)
  • Graph G with n vertices. Integer k (en)
  • Graph coloring, vertex coloring, k-coloring (en)
  • No PTAS unless P = NP (en)
  • O unless P = NP (en)
  • The number P of proper k-colorings of G (en)
dbp:date
  • 2008-04-16 (xsd:date)
  • 2008-07-04 (xsd:date)
dbp:first
  • Alexander (en)
  • Jan (en)
  • William T. (en)
dbp:header
  • Decision (en)
  • Counting problem (en)
  • Optimisation (en)
dbp:headerstyle
  • background: #DD9 (en)
dbp:label
  • Running time (en)
  • Name (en)
  • Complexity (en)
  • Output (en)
  • Input (en)
  • Approximability (en)
  • Garey–Johnson (en)
  • Inapproximability (en)
  • Reduction from (en)
dbp:labelstyle
  • font-weight:normal (en)
dbp:last
  • Mycielski (en)
  • Zykov (en)
  • Tutte (en)
dbp:url
dbp:wikiPageUsesTemplate
dbp:year
  • 1947 (xsd:integer)
  • 1949 (xsd:integer)
  • 1955 (xsd:integer)
dct:subject
gold:hypernym
rdf:type
rdfs:label
  • Graph coloring (en)
  • مسألة تلوين المخطط (ar)
  • Barvení grafu (cs)
  • Coloració de grafs (ca)
  • Χρωματισμός γραφήματος (el)
  • Grafo koloreztaketa (eu)
  • Färbung (Graphentheorie) (de)
  • Coloración de grafos (es)
  • Coloration de graphe (fr)
  • Colorazione dei grafi (it)
  • グラフ彩色 (ja)
  • 그래프 색칠 (ko)
  • Kolorowanie grafu (pl)
  • Kleuren van grafen (nl)
  • Coloração de grafos (pt)
  • Раскраска графов (ru)
  • Розфарбовування графів (uk)
  • Graffärgning (sv)
  • 图着色问题 (zh)
rdfs:seeAlso
owl:sameAs
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:knownFor of
is dbo:wikiPageDisambiguates of
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is dbp:class of
is dbp:knownFor of
is rdfs:seeAlso of
is owl:differentFrom of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 4.0 International