Graph coloring (original) (raw)
Barvení grafu je jednou z disciplín teorie grafů, která se zabývá přiřazováním barev (téměř vždy reprezentovaných přirozenými čísly) různým objektům v grafu – vrcholům, hranám, stěnám atd. Nejčastěji jde o barvení vrcholů, ostatní případy (jako např. barvení sousedících ploch) lze na tento jednoduše převést.
| Property | Value |
|---|---|
| dbo:abstract | En teoria de grafs, la coloració de grafs és un cas especial d', una assignació d'etiquetes tradicionalment anomenades «colors» als elements d'un graf subjecte a certes restriccions. En la seva forma més senzilla, és una manera d'acolorir els vèrtexs d'un graf de tal manera que no n'hi hagi dos de contigus del mateix color; d'això se'n diu coloració de vèrtexs. Similarment, la coloració d'arestes consisteix a assignar un color a cada aresta tal que no n'hi hagi dues d'adjacents del mateix color i la coloració de cares d'un graf planar consisteix a assignar un color a cada cara o regió tal que no hi hagi dues cares del mateix color amb un costat en comú. El punt de partida del tema és la coloració de vèrtexs, ja que la resta de problemes de coloració es poden reduir a una de vèrtexs. Per exemple, la coloració d'arestes d'un graf és tan sols una coloració de vèrtexs del seu i la coloració de cares d'un graf pla és simplement una coloració de vèrtexs del seu dual. Tanmateix, els problemes que no són de coloració de vèrtexs solen estudiar-se tal com són. Això és per una part per la perspectiva i per l'altra perquè certs problemes són més fàcils d'estudiar amb un sistema diferent —la coloració d'arestes n'és un exemple. La convenció d'utilitzar colors prové de la cartografia, on els països o regions s'acoloreixen diferent per distingir-se. Aquest sistema es generalitzà acolorint les cares d'un graf en el pla. Per dualitat planar esdevingué coloració de vèrtexs i d'aquesta forma es generalitza a tots els grafs. En les representacions matemàtiques i computacionals, és habitual usar els primers enters positius o no negatius com a «colors». Més generalment, es pot usar qualsevol conjunt finit com a «conjunt de colors». La coloració de grafs té diverses utilitats pràctiques així com reptes teòrics. A part dels tipus clàssics de problemes, també es poden aplicar diferents limitacions al graf, a l'assignació del color o fins i tot al color en si. Entre el públic general ha assolit popularitat a través del trencaclosques numèric sudoku. La coloració de grafs segueix sent un camp actiu de recerca. (ca) تلوين الرسوم أو تلوين المخطط هو أحد أكثر المسائل شهرة وبحثا في نظرية المخططات، ولها الكثير من التطبيقات العملية وكثير من الحدسيات تتعلق بهذه المسألة وما زال كثير من علماء علوم الحاسوب والرياضيات يحاولون فك هذه الحدسيات. وهذه المسألة هي تخصيص «لون» لأحد عناصر المخطط بحيث تتحقق مجموعة شروط محددة، لعل ابسط الصيغ هذه المسألة هي تلوين رؤوس المخطط بحيث لا يوجد رأسان متجاوران لهما نفس اللون. وهذا النوع من التلوين يسمى «تلوين الرؤوس»، وبشكل مشابه نعرف «تلوين الاضلاع» وهو تلوين الاضلاع بحيث لا يوجد ضلعان يشتركان في رأس لهما نفس اللون، و«تلوين الوجوه» في مخطط مستو هو تخصيص لون لكل وجه أو منطقة بحيث لا يوجد منطقتين تشتركان بنفس الحدود لهما نفس اللون. تلوين الرؤوس عادة هي نقطة الانطلاق ومسائل التلوين الأخرى يمكن تحويلها إلى مسألة تلوين الرؤوس، مثلا «تلوين الأضلاع» هي «تلوين الرؤوس» في الملائم لهذا المخطط، و«تلوين الوجوه» هو «تلوين الرؤوس» للمخطط الثنائي الملائم. ولكن هذه المسائل تدرس كل واحدة على حدا ولا يُنظر إلى هذه العلاقة لعدة أسباب منها أنَّ بعض هذه المسائل يُفضل أن تدرس كما هي لبساطة التعاطي معها كما هي. في الأصل استخدام مصطلح الألوان كان لأجل تلوين الخارطة، ولكن في علم الحاسوب والرياضيات بشكل عام يستخدم الأعداد الصحيحة للدلالة على الألوان. مسألة التلوين هي حالة خاصة من مسألة وسم المخطط. مسألة تلوين المخطط مسألة لها كثير من التطبيقات العملية وتمتد على كل علم الحاسوب، يمكن إضافة شروط على المخطط وأيضا على الألوان، ولعل أكثر نسخة من هذه المسألة شيوعا بين الناس هي لعبة السودوكو. (ar) Barvení grafu je jednou z disciplín teorie grafů, která se zabývá přiřazováním barev (téměř vždy reprezentovaných přirozenými čísly) různým objektům v grafu – vrcholům, hranám, stěnám atd. Nejčastěji jde o barvení vrcholů, ostatní případy (jako např. barvení sousedících ploch) lze na tento jednoduše převést. (cs) Αν G είναι ένα και C ένα σύνολο χρωμάτων, λέμε ότι η απεικόνιση είναι χρωματισμός του G όταν δηλαδή όταν αντιστοιχεί χρώματα στους του G έτσι ώστε κάθε δύο συνδεμένοι κόμβοι να έχουν διαφορετικό χρώμα. Αν το C έχει n διακεκριμένα στοιχεία και ο χρωματισμός f είναι επί, τότε ονομάζεται n-χρωματισμός. Κάθε χρωματισμός διαμερίζει το V(G) σε κλάσεις κόμβων οι οποίοι έχουν κοινό χρώμα. Οι κλάσεις αυτές ονομάζονται χρωματικές κλάσεις. (el) En Teoría de grafos, la coloración de grafos es un caso especial de etiquetado de grafos; es una asignación de etiquetas llamadas colores a elementos del grafo. De manera simple, una coloración de los vértices de un grafo tal que ningún vértice adyacente comparta el mismo color es llamado vértice coloración. Similarmente, una arista coloración asigna colores a cada arista tal que aristas adyacentes no compartan el mismo color, y una coloración de caras de un grafo plano a la asignación de un color a cada cara o región tal que caras que compartan una frontera común tengan colores diferentes.El vértice coloración es el punto de inicio de la coloración, y los otros problemas de coloreo pueden ser transformados a una versión con vértices. Por ejemplo, una arista coloración de un grafo es justamente una vértice coloración del grafo línea respectivo, y una coloración de caras de un grafo plano es una vértice coloración del grafo dual. La convención de usar colores se origina de la coloración de países de un mapa, donde cada cara es literalmente coloreada. Esto fue generalizado a la coloración de caras de grafos inmersos en el plano. En representaciones matemáticas y computacionales se utilizan típicamente enteros no negativos como colores. En general se puede usar un conjunto finito como conjunto de colores. La naturaleza del problema de coloración depende del número de colores pero no sobre cuales son. (es) Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu. In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder „gültigen“ Färbungen (siehe unten), und versucht, Algorithmen zu entwickeln, die für einen vorgegebenen Graphen eine gültige Färbung mit möglichst wenigen Farben finden. Probleme aus der diskreten Mathematik, aber auch außermathematische Fragestellungen lassen sich manchmal in ein Färbungsproblem übersetzen, daher ist die Existenz oder Nichtexistenz solcher Algorithmen auch außerhalb der Graphentheorie von Interesse. (de) In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color. Vertex coloring is often used to introduce graph coloring problems, since other coloring problems can be transformed into a vertex coloring instance. For example, an edge coloring of a graph is just a vertex coloring of its line graph, and a face coloring of a plane graph is just a vertex coloring of its dual. However, non-vertex coloring problems are often stated and studied as-is. This is partly pedagogical, and partly because some problems are best studied in their non-vertex form, as in the case of edge coloring. The convention of using colors originates from coloring the countries of a map, where each face is literally colored. This was generalized to coloring the faces of a graph embedded in the plane. By planar duality it became coloring the vertices, and in this form it generalizes to all graphs. In mathematical and computer representations, it is typical to use the first few positive or non-negative integers as the "colors". In general, one can use any finite set as the "color set". The nature of the coloring problem depends on the number of colors but not on what they are. Graph coloring enjoys many practical applications as well as theoretical challenges. Beside the classical types of problems, different limitations can also be set on the graph, or on the way a color is assigned, or even on the color itself. It has even reached popularity with the general public in the form of the popular number puzzle Sudoku. Graph coloring is still a very active field of research. Note: Many terms used in this article are defined in Glossary of graph theory. (en) Grafo teorian, grafo baten koloreztaketa grafoko elementuak (erpinak edo ertzak) hainbat baldintzapean koloreztatu edo bereizteko erabiltzen da. Erpinen koloreztaketan ondokoak diren erpinak kolore ezberdinez margotu behar dira. Ertzen koloreztaketan berriz ondokoak diren ertzak dira kolore ezberdinez margotu beharrekoak. Grafo bateko aldeei buruz ere koloreztaketa ebazkizunak planteatzen dira. Erpinen koloreztaketa da ordea ebazkizun nagusia, beste koloreztaketa guztiak erpinen koloreztaketaz ebatzi ahal izaten baitira. Grafo koloreztaketak aplikazio zabalak ditu plangintza arloan. Koloreen ordez, zenbakiak edo bestelako ikurrak ere jarri daitezke, baina koloreak erabili ohi dira, historian zehar grafo koloreztaketak mapak koloreztatzeko lau koloreen teoremarekin lotu zirelako. (eu) En théorie des graphes, la coloration de graphe consiste à attribuer une couleur à chacun de ses sommets de manière que deux sommets reliés par une arête soient de couleur différente. On cherche souvent à utiliser le nombre minimal de couleurs, appelé nombre chromatique. La coloration fractionnaire consiste à chercher non plus une mais plusieurs couleurs par sommet et en associant des coûts à chacune. Le champ d'applications de la coloration de graphe couvre notamment le problème de l'attribution de fréquences dans les télécommunications, la conception de puces électroniques ou l'allocation de registres en compilation. (fr) 그래프 이론에서 그래프 색칠(graph色漆, 영어: graph colo(u)ring)은 그래프의 꼭지점들에, 같은 색이 인접하지 않도록 색을 부여하는 방법이다. 이를 사용하여 그래프의 불변량을 정의할 수 있다. (ko) グラフ彩色（英: Graph coloring）とは、グラフの何らかの要素に、ある制約条件を満たすように色を割り当てることである。最も単純なものは、隣接する頂点同士が同じ色にならないように全頂点に彩色する問題である。これを頂点彩色という。同様に辺彩色は、隣接する辺同士が同じ色にならないように全辺を彩色する問題、面彩色は、平面グラフの辺で囲まれた各領域（面）を隣接する面同士が同じ色にならないように彩色する問題である。 (ja) Nella teoria dei grafi, la colorazione dei grafi è un caso speciale di ; è un'assegnazione di etichette, tradizionalmente chiamate "colori", agli elementi di un grafo soggetta a determinati vincoli. Nella sua forma più semplice, è un modo di colorare i vertici di un grafo tale che nessuno dei due vertici adiacenti condivida lo stesso colore; questo prende il nome di colorazione dei vertici. Similmente, una colorazione degli spigoli assegna un colore a ogni spigolo in modo che nessuno dei due spigoli adiacenti condivida lo stesso colore, e una colorazione delle facce di un grafo planare assegna un colore a ogni faccia o regione in modo tale che nessuna delle due facce che condividono un confine abbia lo stesso colore. La colorazione dei vertici è il punto di partenza dell'argomento, e gli altri problemi di colorazione possono essere trasformati in una versione dei vertici. Ad esempio, una colorazione degli spigoli di un grafo è solo una colorazione dei vertici del suo , e una colorazione delle facce di un grafo planare è solo una colorazione dei vertici del suo duale. Tuttavia, i problemi di colorazione dei vertici sono spesso dichiarati e studiati come sono. Questo è in parte per la prospettiva, e in parte perché alcuni problemi si studiano meglio in forma diversa dai vertici, com'è ad esempio la colorazione degli spigoli. La convenzione di usare i colori trae origine dalla colorazione dei paesi di una mappa, dove ogni faccia è colorata in senso letterale. Questo fu poi generalizzato alla colorazione delle facce di un grafo nel piano. A causa della dualità planare si passò alla colorazione dei vertici, e in questa forma si generalizza a tutti i grafi. Nelle rappresentazioni matematiche e informatiche, è tipico usare i primi interi positivi o non negativi come "colori". In generale, si può usare qualsiasi insieme finito come "insieme dei colori". La natura del problema della colorazione dipende dal numero dei colori, ma non da quali sono. La colorazione dei grafi gode di molte applicazioni pratiche come pure di molte sfide teoriche. Oltre ai problemi di tipo classico, si possono anche porre diverse limitazioni sul grafo, o sul modo in cui un colore è assegnato, o perfino sul colore stesso. L'argomento ha raggiunto popolarità anche presso il grande pubblico sotto la forma del popolare rompicapo sudoku. La colorazione dei grafi è ancora un campo di ricerca molto attivo. Nota: molti termini usati in questo articolo sono definiti in Glossario di teoria dei grafi. (it) Het kleuren van grafen is een concept uit de grafentheorie, waarbij men in een niet-gerichte simpele graaf, bestaande uit knopen (vertices, V) die verbonden zijn door kanten (edges, E), aan elke knoop of kant een "kleur" toekent. "Kleur" kan men hier vervangen door "natuurlijk getal"; de term vindt zijn oorsprong in het historische probleem van de kleuring van landkaarten: hoeveel kleuren zijn er minimaal nodig om een kaart te kleuren zodanig dat landen die aan elkaar grenzen steeds een verschillende kleur hebben? (nl) Graffärgning är ett begrepp inom grafteorin i matematiken, som beskriver en tilldelning av färger till antingen kanterna eller noderna uppfyllandet ett visst villkor. Om det är en färgläggning av noderna, kallad en nodfärgning, får inte två noder som har en kant mellan sig vara av samma färg. Om det är en färgläggning av kanterna så får två kanter som möts i en nod inte ha samma färg. (sv) Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично раскраска рёбер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета. Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет. Раскраска вершин — главная задача раскраски графов, все остальные задачи в этой области могут быть сведены к ней. Например, раскраска рёбер графа — это раскраска вершин его рёберного графа, а раскраска областей планарного графа — это раскраска вершин его двойственного графа. Тем не менее, другие проблемы раскраски графов часто ставятся и решаются в изначальной постановке. Причина этого частично заключается в том, что это даёт лучшее представление о происходящем и более показательно, а частично из-за того, что некоторые задачи таким образом решать удобнее (например, раскраска рёбер). Раскраска графов находит применение и во многих практических областях, а не только в теоретических задачах. Помимо классических типов проблем, различные ограничения могут также быть наложены на граф, на способ присвоения цветов или на сами цвета. Этот метод, например, используется в популярной головоломке Судоку. В этой области всё ещё ведутся активные исследования. (ru) Kolorowanie grafu polega w ogólności na przypisaniu określonym elementom składowym grafu (najczęściej wierzchołkom, rzadziej krawędziom lub ścianom) wybranych kolorów według ściśle określonych reguł. Klasyczne (czyli wierzchołkowe) kolorowanie grafu jest związane z przypisaniem wszystkim wierzchołkom w grafie jednej z wybranych barw w ten sposób, aby żadne dwa sąsiednie wierzchołki nie miały tego samego koloru. Innymi słowy, pewne pokolorowanie wierzchołkowe jest poprawne (legalne, dozwolone) wtedy, gdy końcom żadnej krawędzi nie przypisano tego samego koloru. (pl) Em teoria dos grafos, coloração de grafos é um caso especial de ; é uma atribuição de rótulos tradicionalmente chamados "cores" a elementos de um grafo sujeita a certas restrições. Em sua forma mais simples, é uma forma de colorir os vértices de um grafo tal que não haja dois vértices adjacentes que compartilhem a mesma cor; isso é chamado de uma coloração de vértices. Da mesma forma, uma coloração de arestas atribui uma cor para cada aresta de modo que não haja duas arestas adjacentes da mesma cor, e uma coloração de faces de um grafo planar atribui uma cor para cada face ou região de modo que não haja duas faces que compartilham uma fronteira tendo a mesma cor. A coloração de vértices é o ponto de partida para o assunto, e outros problemas de coloração podem ser transformados em uma versão de vértices. Por exemplo, uma coloração de arestas de um grafo é simplesmente uma coloração de vértices do seu , e uma coloração de face de um grafo planar é apenas uma coloração de vértices do seu dual planar. No entanto, problemas de coloração de não-vértices são muitas vezes referidos e estudado como são. Isso se deve em parte à perspectiva, e em parte porque alguns problemas são mais bem estudados na forma não-vértice, como por exemplo, a coloração de arestas. A convenção do uso de cores provém de colorir os países de um mapa, onde cada face é literalmente colorida. Este foi generalizado para coloração das faces de um grafo no plano. Pela dualidade planar se passou a colorir os vértices, e desta forma se generalizou a todos os grafos. Em representações matemáticas e na informática é comum usar os primeiros números inteiros positivos ou não negativos como as "cores". Em geral pode-se usar qualquer conjunto finito como "conjunto de cores". A natureza do problema de coloração depende do número de cores, mas não sobre o que são. A coloração de grafos goza de muitas aplicações práticas, bem como desafios teóricos. Ao lado dos tipos clássicos de problemas, limitações diferentes também podem ser definidas no grafo, ou na forma como uma cor é atribuída, ou mesmo sobre a própria cor. Ela chegou até a se popularizar com o público em geral na forma da popular série de quebra-cabeças Sudoku. A coloração de grafos ainda é um campo de pesquisa muito ativa. (pt) Розфарбуванням простого графу G називають таке приписування кольорів (або натуральних чисел) його вершинам, що ніякі дві суміжні вершини не набувають однакового кольору.Найменшу можливу кількість кольорів у розфарбуванні називають хроматичним числом. (uk) 图着色问题（英語：Graph Coloring Problem，簡稱GCP），又称着色问题，是最著名的NP-完全问题之一。 给定一个无向图，其中为顶点集合，为边集合，图着色问题即为将分为个颜色组，每个组形成一个独立集，即其中没有相邻的顶点。其优化版本是希望获得最小的值。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Petersen_graph_3-coloring.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.math-inst.hu/~p_erdos/1951-01.pdf https://web.archive.org/web/20160310003706/http:/www.math-inst.hu/~p_erdos/1951-01.pdf http://rhydlewis.eu/gcol/ http://www.adaptivebox.net/research/bookmark/gcpcodes_link.html http://www.dcg.ethz.ch/publications/podc08SW.pdf https://graph-coloring.appspot.com/ http://mi.mathnet.ru/msb5974 http://www.mcs.vuw.ac.nz/~djp/tutte/ http://eprints.biblio.unitn.it/119/1/39.pdf http://vispo.com/software http://www.hamilton.ie/ken_duffy/Downloads/cfl.pdf http://www.hamilton.ie/peterc/downloads/rawnet06.pdf https://repository.rothamsted.ac.uk/item/98765/the-design-and-analysis-of-factorial-experiments http://www.dcg.ethz.ch/publications/podcfp107_schneider_188.pdf https://www.springer.com/gb/book/9783319257280 http://portal.acm.org/citation.cfm%3Fid=803884 https://helda.helsinki.fi/handle/10138/21365 http://matwbn.icm.edu.pl/ksiazki/cm/cm3/cm3119.pdf https://webdocs.cs.ualberta.ca/~joe/Coloring/index.html https://docs.lib.purdue.edu/cgi/viewcontent.cgi%3Farticle=1613&context=cstech |
| dbo:wikiPageID | 426743 (xsd:integer) |
| dbo:wikiPageLength | 65121 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1123215305 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Processor_register dbr:Robin_Thomas_(mathematician) dbr:Royal_Society dbr:Message_passing dbr:Mycielskian dbr:NP_(complexity) dbr:Path_coloring dbr:Branch_and_bound dbr:Algebraic_graph_theory dbr:Approximation_algorithm dbr:Paul_Erdős dbr:Paul_Seymour_(mathematician) dbr:Permutation dbr:Cubic_graph dbr:DSatur dbr:University_College_London dbr:Vizing's_theorem dbr:De_Bruijn–Erdős_theorem_(graph_theory) dbr:Defective_coloring dbr:Degree_(graph_theory) dbr:Depth-first_search dbr:Deterministic_algorithm dbr:Incidence_coloring dbr:Independent_set_(graph_theory) dbr:Indifference_graph dbr:Induced_subgraph dbr:Information_Processing_Letters dbr:Information_and_Computation dbr:Interval_edge_coloring dbr:Introduction_to_Algorithms dbr:Kőnig's_theorem_(graph_theory) dbr:L(2,1)-coloring dbr:L(h,_k)-coloring dbr:Register_allocation dbr:Signed_graph dbr:Perfect_elimination_ordering dbc:Graph_coloring dbc:NP-complete_problems dbr:Compiler dbr:Complete_coloring dbr:Complete_graph dbr:Crossing_number_(graph_theory) dbr:Crown_graph dbc:Extensions_and_generalizations_of_graphs dbr:Matching_(graph_theory) dbr:Maximal_independent_set dbr:Petersen_graph dbr:Radio_coloring dbr:Chromatic_polynomial dbr:Circular_coloring dbr:Claude_Berge dbr:Claude_Shannon dbr:Clique_problem dbr:George_David_Birkhoff dbr:Girth_(graph_theory) dbr:Glossary_of_graph_theory dbr:Graph_(discrete_mathematics) dbr:Graph_coloring_game dbr:Graph_homomorphism dbr:Graph_labeling dbr:Graph_minor dbr:Multipartite_graph dbr:NP-complete dbr:NP-hard dbr:Critical_graph dbr:Theory_of_Computing_(journal) dbr:Equitable_coloring dbr:SIAM_Journal_on_Computing dbr:SIAM_Journal_on_Discrete_Mathematics dbr:Oriented_coloring dbr:Line_graph dbr:Linear_time dbr:London_Mathematical_Society dbr:Lovász_number dbr:Star_(graph_theory) dbc:NP-hard_problems dbr:Clique_(graph_theory) dbr:Closed-form_expression dbr:Communications_of_the_ACM dbr:Computer_language dbr:Computer_program dbr:Francis_Guthrie dbr:Frank_Yates dbr:Hadwiger–Nelson_problem dbr:Hamiltonian_coloring dbr:Perfect_graph dbr:Mathematical_Proceedings_of_the_Cambridge_Philosophical_Society dbr:Mathematics_of_Sudoku dbr:Augustus_de_Morgan dbr:Acyclic_coloring dbr:Acyclic_orientation dbr:Adjacent-vertex-distinguishing-total_coloring dbr:Tree_(graph_theory) dbr:Triangle-free_graph dbr:Weak_coloring dbr:Wheel_graph dbr:William_Rowan_Hamilton dbr:Distinguishing_coloring dbr:Distributed_algorithm dbr:Gain_graph dbr:Gallai–Hasse–Roy–Vitaver_theorem dbr:Karp's_21_NP-complete_problems dbr:Lecture_Notes_in_Computer_Science dbr:List_coloring dbr:List_edge-coloring dbr:Pedagogy dbr:Alfred_Kempe dbr:Cycle_graph dbr:Daniel_Brélaz dbr:Dual_graph dbr:Dynamic_programming dbr:Edge_(graph_theory) dbr:Edge_coloring dbr:Erdős–Faber–Lovász_conjecture dbr:Finite_set dbr:Fractional_chromatic_number dbr:Bandwidth_allocation dbr:Breadth-first_search dbr:Bridge_(graph_theory) dbr:Brooks'_theorem dbr:Discrete_Mathematics_(journal) dbr:Four_color_theorem dbr:Fractional_coloring dbr:Graph_automorphism dbr:Graph_embedding dbr:Graph_theory dbr:Isomorphism dbr:Iterated_logarithm dbr:Tree-depth dbr:Ramsey_theory dbr:Rational_point dbr:Recurrence_relation dbr:Group_action_(mathematics) dbr:Hadwiger_conjecture_(graph_theory) dbr:Hajós_construction dbr:Harmonious_coloring dbr:Intersection_graph dbr:Interval_graph dbr:Fibonacci_numbers dbr:Multi-trials_technique dbr:Uniquely_colorable_graph dbr:Arthur_Cayley dbr:ACM_SIGACT_News dbc:Graph_theory dbr:Chordal_graph dbr:Albertson_conjecture dbr:Kenneth_Appel dbr:Bipartite_graph dbc:Computational_problems_in_graph_theory dbr:Symmetric_graph dbr:Symmetry_breaking dbr:Cocoloring dbr:Recursive_largest_first_algorithm dbr:3SAT dbr:Axiom_of_choice dbr:B-coloring dbr:Maria_Chudnovsky dbr:Planar_graph dbr:Planar_graphs dbr:Polynomial dbr:Polynomial-time_approximation_scheme dbr:Greedy_algorithm dbr:Greedy_coloring dbr:Grundy_number dbr:Grötzsch_graph dbr:Edgeless_graph dbr:Polynomial_time dbr:FPRAS dbr:Graph_(graph_theory) dbr:Infinite_graph dbr:Information_theory dbr:Integer dbr:Brute-force_search dbr:Neil_Robertson_(mathematician) dbr:Canadian_Journal_of_Mathematics dbr:RP_(complexity) dbr:Wolfgang_Haken dbr:Heawood dbr:Loop_(graph_theory) dbr:Map dbr:Pattern_matching dbr:Symposium_on_Parallelism_in_Algorithms_and_Architectures dbr:Symposium_on_Theory_of_Computing dbr:Unit_disk_graph dbr:Uzi_Vishkin dbr:Vertex_(graph_theory) dbr:Tutte_polynomial dbr:T-coloring dbr:Euler_characteristic dbr:Computers_and_Intractability:_A_Guide_to_the_Theory_of_NP-Completeness dbr:Strong_perfect_graph_theorem dbr:Sum_coloring dbr:Exact_algorithm dbr:Exact_coloring dbr:Five_color_theorem dbr:Strong_coloring dbr:Sharp-P-complete dbr:Monochromatic_triangle dbr:Symposium_on_Principles_of_Distributed_Computing dbr:Scheduling_(computing) dbr:Semidefinite_programming dbr:Perfectly_orderable_graph dbr:Χ-bounded dbr:SIGPLAN_Symposium_on_Compiler_Construction dbr:Sudoku dbr:Symposium_on_Foundations_of_Computer_Science dbr:Subcoloring dbr:Total_coloring dbr:Star_coloring dbr:Odd_cycle dbr:Unsolved_problems_in_mathematics dbr:Friendship_theorem dbr:Tree_graph dbr:Tutte dbr:Springer-Verlag dbr:P_=_NP dbr:Four_color_conjecture dbr:Inclusion–exclusion dbr:Rank_coloring dbr:Contraction_(graph_theory) dbr:Nowhere-zero_flows dbr:Proceedings_of_the_Cambridge_Philosophical_Society dbr:Information_and_Control dbr:Journal_of_Algorithms dbr:Compiler_optimization dbr:Spanning_tree_(mathematics) dbr:Longest_path dbr:File:Petersen_graph_3-coloring.svg dbr:File:3-coloringEx.svg dbr:File:Chromatic_polynomial_of_all_3-vertex_graphs.png dbr:File:Graph_with_all_three-colourings_2.svg dbr:File:Greedy_colourings.svg dbr:Strong_edge_coloring dbr:Zero-error_capacity |
| dbp:above | Graph coloring (en) |
| dbp:abovestyle | background: #DD9 (en) |
| dbp:authorLink | W. T. Tutte (en) Jan Mycielski (en) Alexander Zykov (en) |
| dbp:data | 3 (xsd:integer) dbr:NP-complete dbr:NP-hard dbr:Sharp-P-complete O (en) Chromatic polynomial (en) Graph G with n vertices. (en) GT4 (en) Does G admit a proper vertex coloring with k colors? (en) Chromatic number (en) FPRAS for restricted cases (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) χ (en) |
| 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) Approximability (en) Complexity (en) Input (en) Output (en) Reduction from (en) Garey–Johnson (en) Inapproximability (en) |
| dbp:labelstyle | font-weight:normal (en) |
| dbp:last | Tutte (en) Mycielski (en) Zykov (en) |
| dbp:wikiPageUsesTemplate | dbt:Anchor dbt:Authority_control dbt:Citation dbt:Citation_needed dbt:Col-begin dbt:Col-break dbt:Col-end dbt:Commons_category dbt:Distinguish dbt:Harv dbt:Harvtxt dbt:Infobox dbt:Main dbt:Math dbt:Mvar dbt:Refbegin dbt:Refend dbt:Reflist dbt:See_also dbt:Short_description dbt:Sub dbt:Sup dbt:Tmath dbt:Vanchor dbt:Harvard_citations dbt:MR dbt:Log-star |
| dbp:year | 1947 (xsd:integer) 1949 (xsd:integer) 1955 (xsd:integer) |
| dct:subject | dbc:Graph_coloring dbc:NP-complete_problems dbc:Extensions_and_generalizations_of_graphs dbc:NP-hard_problems dbc:Graph_theory dbc:Computational_problems_in_graph_theory |
| gold:hypernym | dbr:Case |
| rdf:type | owl:Thing yago:WikicatComputationalProblemsInGraphTheory yago:WikicatNP-completeProblems yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Attribute100024264 yago:Cognition100023271 yago:Concept105835747 yago:Condition113920835 yago:Content105809192 yago:Delay115272029 yago:Difficulty114408086 yago:Event100029378 yago:Extension115272382 yago:Feature105849789 yago:Idea105833840 yago:Invariant105850432 yago:Measure100033615 yago:Pause115271008 yago:Problem114410605 yago:Procedure101023820 yago:Property105849040 yago:PsychologicalFeature100023100 yago:WikicatGraphInvariants yago:YagoPermanentlyLocatedEntity dbo:SupremeCourtOfTheUnitedStatesCase yago:Rule105846932 yago:State100024720 yago:TimeInterval115269513 yago:WikicatDistributedAlgorithms yago:WikicatExtensionsAndGeneralizationsOfGraphs |
| rdfs:comment | Barvení grafu je jednou z disciplín teorie grafů, která se zabývá přiřazováním barev (téměř vždy reprezentovaných přirozenými čísly) různým objektům v grafu – vrcholům, hranám, stěnám atd. Nejčastěji jde o barvení vrcholů, ostatní případy (jako např. barvení sousedících ploch) lze na tento jednoduše převést. (cs) Αν G είναι ένα και C ένα σύνολο χρωμάτων, λέμε ότι η απεικόνιση είναι χρωματισμός του G όταν δηλαδή όταν αντιστοιχεί χρώματα στους του G έτσι ώστε κάθε δύο συνδεμένοι κόμβοι να έχουν διαφορετικό χρώμα. Αν το C έχει n διακεκριμένα στοιχεία και ο χρωματισμός f είναι επί, τότε ονομάζεται n-χρωματισμός. Κάθε χρωματισμός διαμερίζει το V(G) σε κλάσεις κόμβων οι οποίοι έχουν κοινό χρώμα. Οι κλάσεις αυτές ονομάζονται χρωματικές κλάσεις. (el) Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu. In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder „gültigen“ Färbungen (siehe unten), und versucht, Algorithmen zu entwickeln, die für einen vorgegebenen Graphen eine gültige Färbung mit möglichst wenigen Farben finden. Probleme aus der diskreten Mathematik, aber auch außermathematische Fragestellungen lassen sich manchmal in ein Färbungsproblem übersetzen, daher ist die Existenz oder Nichtexistenz solcher Algorithmen auch außerhalb der Graphentheorie von Interesse. (de) Grafo teorian, grafo baten koloreztaketa grafoko elementuak (erpinak edo ertzak) hainbat baldintzapean koloreztatu edo bereizteko erabiltzen da. Erpinen koloreztaketan ondokoak diren erpinak kolore ezberdinez margotu behar dira. Ertzen koloreztaketan berriz ondokoak diren ertzak dira kolore ezberdinez margotu beharrekoak. Grafo bateko aldeei buruz ere koloreztaketa ebazkizunak planteatzen dira. Erpinen koloreztaketa da ordea ebazkizun nagusia, beste koloreztaketa guztiak erpinen koloreztaketaz ebatzi ahal izaten baitira. Grafo koloreztaketak aplikazio zabalak ditu plangintza arloan. Koloreen ordez, zenbakiak edo bestelako ikurrak ere jarri daitezke, baina koloreak erabili ohi dira, historian zehar grafo koloreztaketak mapak koloreztatzeko lau koloreen teoremarekin lotu zirelako. (eu) En théorie des graphes, la coloration de graphe consiste à attribuer une couleur à chacun de ses sommets de manière que deux sommets reliés par une arête soient de couleur différente. On cherche souvent à utiliser le nombre minimal de couleurs, appelé nombre chromatique. La coloration fractionnaire consiste à chercher non plus une mais plusieurs couleurs par sommet et en associant des coûts à chacune. Le champ d'applications de la coloration de graphe couvre notamment le problème de l'attribution de fréquences dans les télécommunications, la conception de puces électroniques ou l'allocation de registres en compilation. (fr) 그래프 이론에서 그래프 색칠(graph色漆, 영어: graph colo(u)ring)은 그래프의 꼭지점들에, 같은 색이 인접하지 않도록 색을 부여하는 방법이다. 이를 사용하여 그래프의 불변량을 정의할 수 있다. (ko) グラフ彩色（英: Graph coloring）とは、グラフの何らかの要素に、ある制約条件を満たすように色を割り当てることである。最も単純なものは、隣接する頂点同士が同じ色にならないように全頂点に彩色する問題である。これを頂点彩色という。同様に辺彩色は、隣接する辺同士が同じ色にならないように全辺を彩色する問題、面彩色は、平面グラフの辺で囲まれた各領域（面）を隣接する面同士が同じ色にならないように彩色する問題である。 (ja) Het kleuren van grafen is een concept uit de grafentheorie, waarbij men in een niet-gerichte simpele graaf, bestaande uit knopen (vertices, V) die verbonden zijn door kanten (edges, E), aan elke knoop of kant een "kleur" toekent. "Kleur" kan men hier vervangen door "natuurlijk getal"; de term vindt zijn oorsprong in het historische probleem van de kleuring van landkaarten: hoeveel kleuren zijn er minimaal nodig om een kaart te kleuren zodanig dat landen die aan elkaar grenzen steeds een verschillende kleur hebben? (nl) Graffärgning är ett begrepp inom grafteorin i matematiken, som beskriver en tilldelning av färger till antingen kanterna eller noderna uppfyllandet ett visst villkor. Om det är en färgläggning av noderna, kallad en nodfärgning, får inte två noder som har en kant mellan sig vara av samma färg. Om det är en färgläggning av kanterna så får två kanter som möts i en nod inte ha samma färg. (sv) Kolorowanie grafu polega w ogólności na przypisaniu określonym elementom składowym grafu (najczęściej wierzchołkom, rzadziej krawędziom lub ścianom) wybranych kolorów według ściśle określonych reguł. Klasyczne (czyli wierzchołkowe) kolorowanie grafu jest związane z przypisaniem wszystkim wierzchołkom w grafie jednej z wybranych barw w ten sposób, aby żadne dwa sąsiednie wierzchołki nie miały tego samego koloru. Innymi słowy, pewne pokolorowanie wierzchołkowe jest poprawne (legalne, dozwolone) wtedy, gdy końcom żadnej krawędzi nie przypisano tego samego koloru. (pl) Розфарбуванням простого графу G називають таке приписування кольорів (або натуральних чисел) його вершинам, що ніякі дві суміжні вершини не набувають однакового кольору.Найменшу можливу кількість кольорів у розфарбуванні називають хроматичним числом. (uk) 图着色问题（英語：Graph Coloring Problem，簡稱GCP），又称着色问题，是最著名的NP-完全问题之一。 给定一个无向图，其中为顶点集合，为边集合，图着色问题即为将分为个颜色组，每个组形成一个独立集，即其中没有相邻的顶点。其优化版本是希望获得最小的值。 (zh) تلوين الرسوم أو تلوين المخطط هو أحد أكثر المسائل شهرة وبحثا في نظرية المخططات، ولها الكثير من التطبيقات العملية وكثير من الحدسيات تتعلق بهذه المسألة وما زال كثير من علماء علوم الحاسوب والرياضيات يحاولون فك هذه الحدسيات. تلوين الرؤوس عادة هي نقطة الانطلاق ومسائل التلوين الأخرى يمكن تحويلها إلى مسألة تلوين الرؤوس، مثلا «تلوين الأضلاع» هي «تلوين الرؤوس» في الملائم لهذا المخطط، و«تلوين الوجوه» هو «تلوين الرؤوس» للمخطط الثنائي الملائم. ولكن هذه المسائل تدرس كل واحدة على حدا ولا يُنظر إلى هذه العلاقة لعدة أسباب منها أنَّ بعض هذه المسائل يُفضل أن تدرس كما هي لبساطة التعاطي معها كما هي. (ar) En teoria de grafs, la coloració de grafs és un cas especial d', una assignació d'etiquetes tradicionalment anomenades «colors» als elements d'un graf subjecte a certes restriccions. En la seva forma més senzilla, és una manera d'acolorir els vèrtexs d'un graf de tal manera que no n'hi hagi dos de contigus del mateix color; d'això se'n diu coloració de vèrtexs. Similarment, la coloració d'arestes consisteix a assignar un color a cada aresta tal que no n'hi hagi dues d'adjacents del mateix color i la coloració de cares d'un graf planar consisteix a assignar un color a cada cara o regió tal que no hi hagi dues cares del mateix color amb un costat en comú. (ca) In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color. (en) En Teoría de grafos, la coloración de grafos es un caso especial de etiquetado de grafos; es una asignación de etiquetas llamadas colores a elementos del grafo. De manera simple, una coloración de los vértices de un grafo tal que ningún vértice adyacente comparta el mismo color es llamado vértice coloración. Similarmente, una arista coloración asigna colores a cada arista tal que aristas adyacentes no compartan el mismo color, y una coloración de caras de un grafo plano a la asignación de un color a cada cara o región tal que caras que compartan una frontera común tengan colores diferentes.El vértice coloración es el punto de inicio de la coloración, y los otros problemas de coloreo pueden ser transformados a una versión con vértices. Por ejemplo, una arista coloración de un grafo es justa (es) Nella teoria dei grafi, la colorazione dei grafi è un caso speciale di ; è un'assegnazione di etichette, tradizionalmente chiamate "colori", agli elementi di un grafo soggetta a determinati vincoli. Nella sua forma più semplice, è un modo di colorare i vertici di un grafo tale che nessuno dei due vertici adiacenti condivida lo stesso colore; questo prende il nome di colorazione dei vertici. Similmente, una colorazione degli spigoli assegna un colore a ogni spigolo in modo che nessuno dei due spigoli adiacenti condivida lo stesso colore, e una colorazione delle facce di un grafo planare assegna un colore a ogni faccia o regione in modo tale che nessuna delle due facce che condividono un confine abbia lo stesso colore. (it) Em teoria dos grafos, coloração de grafos é um caso especial de ; é uma atribuição de rótulos tradicionalmente chamados "cores" a elementos de um grafo sujeita a certas restrições. Em sua forma mais simples, é uma forma de colorir os vértices de um grafo tal que não haja dois vértices adjacentes que compartilhem a mesma cor; isso é chamado de uma coloração de vértices. Da mesma forma, uma coloração de arestas atribui uma cor para cada aresta de modo que não haja duas arestas adjacentes da mesma cor, e uma coloração de faces de um grafo planar atribui uma cor para cada face ou região de modo que não haja duas faces que compartilham uma fronteira tendo a mesma cor. (pt) Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично раскраска рёбер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета. Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет. (ru) |
| rdfs:label | Graph coloring (en) مسألة تلوين المخطط (ar) Coloració de grafs (ca) Barvení grafu (cs) Färbung (Graphentheorie) (de) Χρωματισμός γραφήματος (el) Grafo koloreztaketa (eu) Coloración de grafos (es) Colorazione dei grafi (it) Coloration de graphe (fr) 그래프 색칠 (ko) グラフ彩色 (ja) Kolorowanie grafu (pl) Kleuren van grafen (nl) Раскраска графов (ru) Coloração de grafos (pt) Graffärgning (sv) Розфарбовування графів (uk) 图着色问题 (zh) |
| rdfs:seeAlso | dbr:History_of_the_four_color_theorem |
| owl:differentFrom | dbr:Edge_coloring |
| owl:sameAs | freebase:Graph coloring yago-res:Graph coloring wikidata:Graph coloring dbpedia-ar:Graph coloring dbpedia-ca:Graph coloring dbpedia-cs:Graph coloring dbpedia-cy:Graph coloring dbpedia-de:Graph coloring dbpedia-el:Graph coloring dbpedia-es:Graph coloring dbpedia-et:Graph coloring dbpedia-eu:Graph coloring dbpedia-fa:Graph coloring dbpedia-fr:Graph coloring dbpedia-he:Graph coloring dbpedia-hr:Graph coloring dbpedia-hu:Graph coloring http://hy.dbpedia.org/resource/Գրաֆների_ներկում dbpedia-it:Graph coloring dbpedia-ja:Graph coloring dbpedia-ko:Graph coloring http://lt.dbpedia.org/resource/Grafo_spalvinimas dbpedia-nl:Graph coloring dbpedia-no:Graph coloring dbpedia-pl:Graph coloring dbpedia-pt:Graph coloring dbpedia-ro:Graph coloring dbpedia-ru:Graph coloring dbpedia-simple:Graph coloring dbpedia-sk:Graph coloring dbpedia-sr:Graph coloring dbpedia-sv:Graph coloring http://ta.dbpedia.org/resource/கோட்டுரு_நிறந்தீட்டல் dbpedia-th:Graph coloring dbpedia-uk:Graph coloring http://ur.dbpedia.org/resource/لونی_کثیر_رقمی dbpedia-vi:Graph coloring dbpedia-zh:Graph coloring https://global.dbpedia.org/id/4gVdE |
| prov:wasDerivedFrom | wikipedia-en:Graph_coloring?oldid=1123215305&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/3-coloringEx.svg wiki-commons:Special:FilePath/Chromatic_polynomial_of_all_3-vertex_graphs.png wiki-commons:Special:FilePath/Graph_with_all_three-colourings_2.svg wiki-commons:Special:FilePath/Greedy_colourings.svg wiki-commons:Special:FilePath/Petersen_graph_3-coloring.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Graph_coloring |
| is dbo:knownFor of | dbr:S._A._Choudum |
| is dbo:wikiPageDisambiguates of | dbr:Coloring |
| is dbo:wikiPageRedirects of | dbr:Decentralized_graph_coloring dbr:K-colouring dbr:Computational_complexity_of_graph_coloring dbr:Chromatic_number dbr:Graph_colouring dbr:Applications_of_graph_coloring dbr:Colored_graph dbr:Distributed_graph_coloring dbr:Cole-Vishkin_algorithm dbr:Vertex_chromatic_number dbr:Cole–Vishkin_algorithm dbr:Face_coloring dbr:Graph_Colouring dbr:Graph_Two-Coloring dbr:Graph_color dbr:Graph_coloration dbr:Graph_coloring_algorithm dbr:Graph_coloring_problem dbr:Graph_colouring_problem dbr:Graph_colouring_problems dbr:Graph_two-coloring dbr:Algorithms_for_graph_coloring dbr:Unlabeled_coloring dbr:Proper_coloring dbr:Two-colorable_graph dbr:Vector_chromatic_number dbr:Parallel_algorithms_for_graph_coloring dbr:Mycielski's_theorem dbr:3-colourability dbr:Three-Colorable_Graph dbr:Three-colorable_graph dbr:Vertex-colouring dbr:Vertex_color dbr:Vertex_coloring dbr:Vertex_colouring dbr:Coloring_algorithm dbr:Coloring_problem dbr:Colourability dbr:Colouring_algorithm dbr:Colouring_problem dbr:K-chromatic_graph dbr:K-colorable dbr:K-coloring dbr:K-vertex_colorable dbr:Network_coloring dbr:Network_colouring |
| is dbo:wikiPageWikiLink of | dbr:Belief_propagation dbr:Probabilistic_method dbr:Queen's_graph dbr:Robin_Wilson_(mathematician) dbr:Rook's_graph dbr:Elementary_Number_Theory,_Group_Theory_and_Ramanujan_Graphs dbr:Mirsky's_theorem dbr:Moser_spindle dbr:Nowhere-zero_flow dbr:Memetic_algorithm dbr:Path_coloring dbr:Barnette's_conjecture dbr:Book_embedding dbr:David_Eppstein dbr:Decentralized_graph_coloring dbr:Algebraic_graph_theory dbr:András_Hajnal dbr:Answer_set_programming dbr:Apollonian_network dbr:Approximation_algorithm dbr:Hypercube_graph dbr:Betweenness dbr:Pathwidth dbr:Paul_A._Catlin dbr:Periodic_graph_(crystallography) dbr:Regular_dodecahedron dbr:Regular_icosahedron dbr:Cycle_double_cover dbr:Cycle_space dbr:DSatur dbr:Unit_distance_graph dbr:Voltage_graph dbr:De_Bruijn–Erdős_theorem_(graph_theory) dbr:Decision_Model_and_Notation dbr:Defective_coloring dbr:Incidence_(graph) dbr:Incidence_coloring dbr:Independent_set_(graph_theory) dbr:Indifference_graph dbr:L(h,_k)-coloring dbr:Register_allocation dbr:Universal_algebra dbr:Lexicographic_breadth-first_search dbr:Lieb's_square_ice_constant dbr:Pearls_in_Graph_Theory dbr:Penny_graph dbr:K-colouring dbr:Precoloring_extension dbr:Signed_graph dbr:Pseudoforest dbr:♯P-complete dbr:1-planar_graph dbr:110-vertex_Iofinova-Ivanov_graph dbr:Complete_coloring dbr:Computational_complexity_of_graph_coloring dbr:S._A._Choudum dbr:SL_(complexity) dbr:Elizabeth_Wilmer dbr:Orientation_(graph_theory) dbr:Petersen_graph dbr:Radio_coloring dbr:Zdeněk_Dvořák dbr:Chromatic_number dbr:Chromatic_polynomial dbr:Circular_coloring dbr:Claude_Berge dbr:Clique-width dbr:Frankl–Rödl_graph dbr:Gary_Chartrand dbr:Glossary_of_graph_theory dbr:Graph_coloring_game dbr:Graph_colouring dbr:Graph_homomorphism dbr:Graph_minor dbr:Graph_power dbr:Branch_and_price dbr:Multipartite_graph dbr:Conflict-free_coloring dbr:Constraint_satisfaction dbr:Constraint_satisfaction_problem dbr:Critical_graph dbr:Equidissection dbr:Equitable_coloring dbr:Erdős_on_Graphs dbr:Oriented_coloring dbr:Apex_graph dbr:Applications_of_graph_coloring dbr:Chordal_completion dbr:Snark_(graph_theory) dbr:Claw-free_graph dbr:Clebsch_graph dbr:Clique_cover dbr:Colored_graph dbr:Combinatorics dbr:Comparability_graph dbr:Complexity_of_constraint_satisfaction dbr:Emanuels_Grīnbergs dbr:Fred_Galvin dbr:Frucht's_theorem dbr:Hadwiger_conjecture_(combinatorial_geometry) dbr:Hamiltonian_coloring dbr:Hardware_watermarking dbr:Hortensia_Galeana_Sánchez dbr:Kristina_Vušković dbr:Perfect_graph dbr:Maekawa's_theorem dbr:Maker-Breaker_game dbr:Split_(graph_theory) dbr:Mathematics_of_Sudoku dbr:Meyniel_graph dbr:Bruce_Reed_(mathematician) dbr:Acyclic_coloring dbr:Acyclic_orientation dbr:Agnes_M._Herzberg dbr:Treewidth dbr:Triangle-free_graph dbr:Disjunctive_graph dbr:Distinguishing_coloring dbr:Distributed_constraint_optimization dbr:Distributed_graph_coloring dbr:Dually_chordal_graph dbr:Gabriela_Araujo-Pardo dbr:Gadget_(computer_science) dbr:Gallai–Hasse–Roy–Vitaver_theorem dbr:Cole-Vishkin_algorithm dbr:Colorable dbr:Coloring dbr:Heawood_conjecture dbr:Janson_inequality dbr:Karp's_21_NP-complete_problems dbr:Latin_square dbr:Linear_forest dbr:Linear_programming_relaxation dbr:List_coloring dbr:List_edge-coloring dbr:5 dbr:Daniel_Kráľ dbr:Dual_graph dbr:Edge-transitive_graph dbr:Edge_coloring dbr:Amanda_Montejano dbr:Erdős–Faber–Lovász_conjecture dbr:Erdős–Ko–Rado_theorem dbr:Eugene_Lawler dbr:Expander_graph dbr:Brooks'_theorem dbr:Brouwer–Haemers_graph dbr:No-three-in-line_problem dbr:Outerplanar_graph dbr:Pancake_graph dbr:Parity_of_zero dbr:Cavity_method dbr:Cayley_graph dbr:Dilworth's_theorem dbr:Discharging_method_(discrete_mathematics) dbr:Four_color_theorem dbr:Fractional_coloring dbr:Goldberg–Seymour_conjecture dbr:Golomb_graph dbr:Graph_Theory,_1736–1936 dbr:Graph_cuts_in_computer_vision dbr:Graph_theory dbr:Iterated_logarithm dbr:John_R._Isbell dbr:Lenore_Cowen dbr:Map_coloring dbr:Self-organized_criticality dbr:Vertex_chromatic_number dbr:List_of_NP-complete_problems dbr:Tree-depth dbr:Maria_Hasse dbr:Walter_Gottschalk dbr:Quadratic_unconstrained_binary_optimization dbr:Routing_and_wavelength_assignment dbr:Gregory_Chaitin dbr:Grötzsch's_theorem dbr:Hadwiger_conjecture_(graph_theory) dbr:Hadwiger_number dbr:Hajós_construction dbr:Hall-type_theorems_for_hypergraphs dbr:Hanoi_graph dbr:Hedetniemi's_conjecture dbr:HeuristicLab dbr:Interval_graph dbr:James_Earl_Baumgartner dbr:Bag_(puzzle) dbr:Courcelle's_theorem dbr:Uniquely_colorable_graph dbr:Tolerance_graph dbr:Arrangement_of_lines dbr:Art_gallery_problem dbr:Chordal_graph dbr:Albertson_conjecture dbr:Katalin_Vesztergombi dbr:LLVM dbr:Bipartite_graph dbr:Cocoloring dbr:Cograph dbr:Col_(game) dbr:Cole–Vishkin_algorithm dbr:Colin_de_Verdière_graph_invariant dbr:Ebadollah_S._Mahmoodian dbr:Herbert_Grötzsch dbr:Hereditary_property dbr:Java_performance dbr:Tietze's_graph dbr:Reconfiguration dbr:Distance-hereditary_graph dbr:3-coloring dbr:Art_Gallery_Theorems_and_Algorithms dbr:B-coloring dbr:Markov_chain_mixing_time dbr:Bojan_Mohar dbr:Boolean_prime_ideal_theorem dbr:Boolean_satisfiability_problem dbr:Planar_graph dbr:Split_graph dbr:Splittance dbr:Greedy_coloring dbr:Hugo_Hadwiger dbr:Face_coloring dbr:Graph_Colouring dbr:Graph_Two-Coloring dbr:Graph_color dbr:Graph_coloration dbr:Graph_coloring_algorithm dbr:Graph_coloring_problem dbr:Graph_colouring_problem dbr:Graph_colouring_problems dbr:Graph_two-coloring dbr:Incidence_structure dbr:Algorithms_for_graph_coloring dbr:Mihalis_Yannakakis dbr:Neil_Robertson_(mathematician) dbr:Order_polynomial dbr:Rainbow-independent_set dbr:Cereceda's_conjecture dbr:Chaitin's_algorithm dbr:Shadow_Madness dbr:Chromatic_(disambiguation) dbr:Longest_path_problem dbr:SNP_(complexity) dbr:Static_single-assignment_form dbr:Margit_Voigt dbr:Unavoidable_pattern dbr:Unit_disk_graph dbr:Uzi_Vishkin dbr:Tutte_polynomial dbr:T-coloring dbr:Tom_Hull_(mathematician) dbr:Using_the_Borsuk–Ulam_Theorem dbr:Expander_mixing_lemma dbr:Exponential_time_hypothesis dbr:FKG_inequality dbr:Factor-critical_graph dbr:Gyárfás–Sumner_conjecture dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Strong_perfect_graph_theorem dbr:Sudoku_graph dbr:The_Mathematical_Coloring_Book dbr:Even-hole-free_graph dbr:Exact_coloring dbr:Quartic_graph dbr:Strong_coloring dbr:Schnyder's_theorem dbr:Sumner's_conjecture dbr:Polyhedra_(book) dbr:Nonblocker dbr:Packing_in_a_hypergraph dbr:Perfect_graph_theorem dbr:Shift_graph dbr:The_Petersen_Graph dbr:Χ-bounded dbr:Sudoku dbr:Parameterized_complexity dbr:Property_testing dbr:Van_der_Waerden_number dbr:Scheinerman's_conjecture dbr:Subcoloring dbr:Slicing_the_Truth dbr:Symmetric_hypergraph_theorem dbr:Set_splitting_problem dbr:Total_coloring dbr:Star_coloring dbr:Twin-width dbr:Road_coloring_theorem dbr:Word-representable_graph dbr:Tricolorability dbr:Taking_Sudoku_Seriously dbr:Unlabeled_coloring dbr:Proper_coloring dbr:Two-colorable_graph dbr:Vector_chromatic_number dbr:Parallel_algorithms_for_graph_coloring dbr:Mycielski's_theorem dbr:3-colourability dbr:Three-Colorable_Graph dbr:Three-colorable_graph dbr:Vertex-colouring dbr:Vertex_color |
| is dbp:class of | dbr:DSatur |
| is dbp:knownFor of | dbr:S._A._Choudum |
| is rdfs:seeAlso of | dbr:Register_allocation |
| is foaf:primaryTopic of | wikipedia-en:Graph_coloring |
