Chromatic polynomial
http://dbpedia.org/resource/Chromatic_polynomial an entity of type: Abstraction100002137
The chromatic polynomial is a graph polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally defined by George David Birkhoff to study the four color problem. It was generalised to the Tutte polynomial by Hassler Whitney and W. T. Tutte, linking it to the Potts model of statistical physics.
rdf:langString
Das chromatische Polynom gibt zu einem Graphen die Anzahl der möglichen Knotenfärbungen mit Farben an, d. h. die Anzahl der Färbung aller Knoten des Graphen, so dass Knoten, die durch eine Kante verbunden sind, verschiedene Farben tragen.
rdf:langString
De chromatische veelterm van een graaf geeft het aantal mogelijke geldige knopenkleuringen met kleuren, dit is het aantal kleuringen van de knopen van de graaf zodanig dat twee knopen die door een kant verbonden zijn steeds een andere kleur hebben. Het is niet nodig dat alle kleuren gebruikt worden, zolang maar aan deze voorwaarde voldaan is. Dat de functie inderdaad een veelterm is voor elke graaf kan inductief bewezen worden.
rdf:langString
Il polinomio cromatico è un polinomio studiato nella teoria algebrica dei grafi, una branca della matematica. Esso conta il numero di colorazioni dei grafi come funzione del numero dei colori e fu definito originariamente da George David Birkhoff per affrontare il problema dei quattro colori. Fu generalizzato al da H. Whitney e W. T. Tutte, legandolo al della fisica statistica.
rdf:langString
Det kromatiska polynomet för en graf är ett begrepp inom matematiken, speciellt grafteorin. Låt vara en graf. Då är det kromatiska polynomet det polynom som anger på hur många sätt kan färgläggas med färger. Att det finns en sådan funktion för varje graf är uppenbart men att det faktiskt är ett polynom för varje given graf är inte lika självklart men ändå sant.
rdf:langString
Хроматический многочлен — многочлен, изучаемый в алгебраической теории графов, представляющий число раскрасок графа как функцию от числа цветов. Первоначально определён Джорджем Биркгофов для попытки решения на проблемы четырёх красок. Обобщен и систематически изучен Хасслером Уитни, Татт обобщил хроматический многочлен до многочлена Татта, связав его с статистической физики.
rdf:langString
Хромати́чний многочле́н — многочлен, досліджуваний в алгебричній теорії графів, що подає число розфарбувань графа як функцію від кількості кольорів. Спочатку його визначив Джордж Біркгоф для спроби розв'язання проблеми чотирьох фарб. Узагальнив та систематично вивчив , Татт узагальнив хроматичний многочлен до многочлена Татта, пов'язавши його з статистичної фізики.
rdf:langString
在代数图论中，色多项式是乔治·戴维·伯克霍夫为了尝试证明四色定理而定义的一种多项式。 色多项式的值是在图中顶点的不同的-着色数目，是关于的多项式。 例如当图为一点时，。
rdf:langString
En mathématiques, plus particulièrement en théorie des graphes, le polynôme chromatique d'un graphe est une fonction polynômiale donnant le nombre de colorations distinctes d'un graphe, en fonction du nombre de couleurs autorisées. Il a été introduit d'abord en 1912 pour les graphes planaires, par George David Birkhoff, qui cherchait à démontrer le théorème des quatre couleurs. Ce polynôme a pour racines tous les entiers positifs ou nuls strictement inférieurs au nombre chromatique du graphe et a pour degré l'ordre du graphe.
rdf:langString
rdf:langString
Chromatic polynomial
rdf:langString
Chromatisches Polynom
rdf:langString
Polinomio cromatico
rdf:langString
Polynôme chromatique
rdf:langString
Chromatische veelterm
rdf:langString
Хроматический многочлен
rdf:langString
Kromatiskt polynom
rdf:langString
Хроматичний многочлен
rdf:langString
色多项式
xsd:integer
1460126
xsd:integer
1099989123
rdf:langString
#k-colorings
rdf:langString
Chromatic polynomial
rdf:langString
#3SAT
rdf:langString
#P-hard
rdf:langString
#P-hard unless
rdf:langString
Coefficients of
rdf:langString
Graph G with n vertices.
rdf:langString
In P for . for . Otherwise
for some constant
rdf:langString
No FPRAS for
rdf:langString
for some constant
rdf:langString
Running time
rdf:langString
Approximability
rdf:langString
Complexity
rdf:langString
Input
rdf:langString
Output
rdf:langString
Reduction from
rdf:langString
Chromatic polynomial
rdf:langString
ChromaticPolynomial
rdf:langString
font-weight:normal
rdf:langString
cs2
rdf:langString
The chromatic polynomial is a graph polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally defined by George David Birkhoff to study the four color problem. It was generalised to the Tutte polynomial by Hassler Whitney and W. T. Tutte, linking it to the Potts model of statistical physics.
rdf:langString
Das chromatische Polynom gibt zu einem Graphen die Anzahl der möglichen Knotenfärbungen mit Farben an, d. h. die Anzahl der Färbung aller Knoten des Graphen, so dass Knoten, die durch eine Kante verbunden sind, verschiedene Farben tragen.
rdf:langString
En mathématiques, plus particulièrement en théorie des graphes, le polynôme chromatique d'un graphe est une fonction polynômiale donnant le nombre de colorations distinctes d'un graphe, en fonction du nombre de couleurs autorisées. Il a été introduit d'abord en 1912 pour les graphes planaires, par George David Birkhoff, qui cherchait à démontrer le théorème des quatre couleurs. Ce polynôme a pour racines tous les entiers positifs ou nuls strictement inférieurs au nombre chromatique du graphe et a pour degré l'ordre du graphe. Le polynôme chromatique d'un graphe est un invariant, c'est-à-dire une propriété dépendant uniquement de sa structure et indépendante de son étiquetage. Autrement dit, deux graphes isomorphes auront le même polynôme chromatique. Le terme de chromatiquement équivalent est employé pour désigner des graphes ayant le même polynôme chromatique. À l'opposé, un graphe chromatiquement unique est déterminé par son polynôme chromatique.
rdf:langString
De chromatische veelterm van een graaf geeft het aantal mogelijke geldige knopenkleuringen met kleuren, dit is het aantal kleuringen van de knopen van de graaf zodanig dat twee knopen die door een kant verbonden zijn steeds een andere kleur hebben. Het is niet nodig dat alle kleuren gebruikt worden, zolang maar aan deze voorwaarde voldaan is. Dat de functie inderdaad een veelterm is voor elke graaf kan inductief bewezen worden.
rdf:langString
Il polinomio cromatico è un polinomio studiato nella teoria algebrica dei grafi, una branca della matematica. Esso conta il numero di colorazioni dei grafi come funzione del numero dei colori e fu definito originariamente da George David Birkhoff per affrontare il problema dei quattro colori. Fu generalizzato al da H. Whitney e W. T. Tutte, legandolo al della fisica statistica.
rdf:langString
Det kromatiska polynomet för en graf är ett begrepp inom matematiken, speciellt grafteorin. Låt vara en graf. Då är det kromatiska polynomet det polynom som anger på hur många sätt kan färgläggas med färger. Att det finns en sådan funktion för varje graf är uppenbart men att det faktiskt är ett polynom för varje given graf är inte lika självklart men ändå sant.
rdf:langString
Хроматический многочлен — многочлен, изучаемый в алгебраической теории графов, представляющий число раскрасок графа как функцию от числа цветов. Первоначально определён Джорджем Биркгофов для попытки решения на проблемы четырёх красок. Обобщен и систематически изучен Хасслером Уитни, Татт обобщил хроматический многочлен до многочлена Татта, связав его с статистической физики.
rdf:langString
Хромати́чний многочле́н — многочлен, досліджуваний в алгебричній теорії графів, що подає число розфарбувань графа як функцію від кількості кольорів. Спочатку його визначив Джордж Біркгоф для спроби розв'язання проблеми чотирьох фарб. Узагальнив та систематично вивчив , Татт узагальнив хроматичний многочлен до многочлена Татта, пов'язавши його з статистичної фізики.
rdf:langString
在代数图论中，色多项式是乔治·戴维·伯克霍夫为了尝试证明四色定理而定义的一种多项式。 色多项式的值是在图中顶点的不同的-着色数目，是关于的多项式。 例如当图为一点时，。
rdf:langString
background: #DD9; font-size: 125%;
xsd:nonNegativeInteger
28884
