About: Chromatic polynomial

Property	Value
dbo:description	gráfelméleti fogalom (hu) Anzahl der möglichen Knotenfärbungen in der Graphentheorie (de) polynomial defined from a node-link graph, that counts the number of graph colorings as a function of the number of colors (en) многочлен, считающий кол-во раскрасок графа (ru) многочлен, що подає число розмальовок графа як функцію від кількості кольорів (uk) polinomio studiato nella teoria algebrica dei grafi (it)
dbo:thumbnail	wiki-commons:Special:FilePath/Chromatic_polynomial_of_all_3-vertex_graphs_BW.png?width=300
dbo:wikiPageExternalLink	http://planetmath.org/encyclopedia/ChromaticPolynomial.html https://archive.today/20121220104146/http:/www.ecs.vuw.ac.nz/~djp/tutte/ http://math.mit.edu/~rstan/pubs/pubfiles/18.pdf http://dml.cz/bitstream/handle/10338.dmlcz/128421/CzechMathJ_43-1993-3_10.pdf
dbo:wikiPageWikiLink	dbr:PlanetMath dbc:Graph_invariants dbr:Hassler_Whitney dbr:Complex_plane dbr:Ronald_C._Read dbr:Tutte_polynomial dbr:Abstract_algebra dbr:Edge_contraction dbr:W._T._Tutte dbr:Independent_set_(graph_theory) dbr:Branch_and_bound dbr:Mathematics dbr:Cycle_graph dbr:Chordal_graph dbr:Petersen_graph dbr:Falling_factorial dbr:Categorification dbr:Mathematical_analysis dbr:Isomorphism dbr:Strong_induction dbr:Graph_coloring dbr:Monic_polynomial dbr:Acyclic_orientation dbr:Clique-sum dbr:Cograph dbr:Golden_ratio dbr:Stirling_number dbr:Partition_of_a_set dbr:Statistical_physics dbr:Computational_complexity_theory dbr:Connected_component_(graph_theory) dbr:Sharp-P dbr:Complete_graph dbr:Polynomial dbr:Outerplanar_graph dbr:Journal_of_Combinatorial_Theory dbr:Discrete_Mathematics_(journal) dbc:Graph_coloring dbr:Four_color_theorem dbr:Path_graph dbr:Edgeless_graph dbr:George_David_Birkhoff dbr:Planar_graph dbr:Graph_automorphism dbr:Clique-width dbr:Algebraic_graph_theory dbr:Potts_model dbr:Khovanov_homology dbr:Deletion–contraction_formula dbr:Root_of_a_function dbr:Claw_(graph_theory) dbr:Decision_problem dbr:Arrangement_of_hyperplanes dbr:Graph_polynomial dbr:Approximation_algorithms dbr:Combinatorics,_Probability_and_Computing dbr:Fibonacci_numbers dbr:NP-hard dbr:Graph_invariant dbr:Logarithmically_concave_sequence dbr:Mathematica dbr:NP_(complexity_class) dbr:P_(complexity_class) dbr:File:Chromatically_equivalent_graphs.svg dbr:Chromatic_invariant dbr:File:Chromatic_polynomial_of_all_3-vertex_graphs_BW.png dbr:File:Chromatic_polynomial_of_all_3-vertex_graphs_BW_with_colorings.png dbr:Deletion-contraction_formula dbr:Deletion-contraction_recurrence dbr:Four_color_problem dbr:FPRAS dbr:Interpolating_polynomial dbr:Spanning_tree_(mathematics) dbr:RP_(complexity_class) dbr:Tree-width dbr:Tree_graph dbr:Tutte dbr:Vertex_coloring
dbp:above	Chromatic polynomial (en) #k-colorings (en)
dbp:abovestyle	background: #DD9; font-size: 125%; (en)
dbp:data	Graph G with n vertices. (en) #3SAT (en) #P-hard (en) #P-hard unless (en) Coefficients of (en) In P for . for . Otherwise for some constant (en) No FPRAS for (en) for some constant (en)
dbp:date	2008-08-20 (xsd:date)
dbp:label	Complexity (en) Approximability (en) Input (en) Output (en) Reduction from (en) Running time (en)
dbp:labelstyle	font-weight:normal (en)
dbp:mode	cs2 (en)
dbp:title	Chromatic polynomial (en)
dbp:url	https://web.archive.org/web/20080820122306/http:/planetmath.org/encyclopedia/ChromaticPolynomial.html
dbp:urlname	ChromaticPolynomial (en)
dbp:wikiPageUsesTemplate	dbt:Main dbt:Center dbt:Reflist dbt:Math dbt:Infobox dbt:Sup dbt:Citation dbt:Refend dbt:MathWorld dbt:Refbegin dbt:Webarchive dbt:Short_description
dct:subject	dbc:Graph_invariants dbc:Graph_coloring
rdfs:label	Chromatic polynomial (en) Chromatisches Polynom (de) Polinomio cromatico (it) Polynôme chromatique (fr) Chromatische veelterm (nl) Хроматический многочлен (ru) Kromatiskt polynom (sv) Хроматичний многочлен (uk) 色多项式 (zh)
owl:sameAs	yago-res:Chromatic polynomial freebase:Chromatic polynomial wikidata:Chromatic polynomial dbpedia-it:Chromatic polynomial dbpedia-nl:Chromatic polynomial dbpedia-de:Chromatic polynomial dbpedia-fr:Chromatic polynomial dbpedia-zh:Chromatic polynomial dbpedia-hu:Chromatic polynomial dbpedia-ru:Chromatic polynomial dbpedia-sv:Chromatic polynomial dbpedia-vi:Chromatic polynomial dbpedia-uk:Chromatic polynomial dbpedia-global:Chromatic polynomial dbr:Chromatic polynomial
prov:wasDerivedFrom	wikipedia-en:Chromatic_polynomial?oldid=1290378321&ns=0
foaf:depiction	wiki-commons:Special:FilePath/Chromatic_polynomial_of_all_3-vertex_graphs_BW.png wiki-commons:Special:FilePath/Chromatic_polynomial_...3-vertex_graphs_BW_with_colorings.png wiki-commons:Special:FilePath/Chromatically_equivalent_graphs.svg
foaf:isPrimaryTopicOf	wikipedia-en:Chromatic_polynomial
is dbo:wikiPageDisambiguates of	dbr:Chromatic_(disambiguation)
is dbo:wikiPageWikiLink of	dbr:Signed_graph dbr:Mixed_graph dbr:Graph_property dbr:Turán_graph dbr:Wheel_graph dbr:Ronald_C._Read dbr:Tutte_polynomial dbr:Edge_contraction dbr:Beraha_constants dbr:Friendship_graph dbr:Combinatorics dbr:Chromatic_(disambiguation) dbr:Chordal_graph dbr:Petersen_graph dbr:Directed_acyclic_graph dbr:Matroid dbr:Graph_coloring dbr:Acyclic_orientation dbr:Ladder_graph dbr:Ruth_Aaronson_Bari dbr:Polynomial dbr:Random_graph dbr:Brinkmann_graph dbr:Bull_graph dbr:Pappus_graph dbr:Inclusion–exclusion_principle dbr:Component_(graph_theory) dbr:Discrete_Mathematics_(journal) dbr:List_of_graph_theory_topics dbr:George_David_Birkhoff dbr:Alan_Sokal dbr:Algebraic_graph_theory dbr:Potts_model dbr:Deletion–contraction_formula dbr:Reconstruction_conjecture dbr:Windmill_graph dbr:Graph_polynomial dbr:Read's_conjecture dbr:June_Huh dbr:Agnes_M._Herzberg dbr:Order_polynomial
is foaf:primaryTopic of	wikipedia-en:Chromatic_polynomial