Equitable coloring (original) (raw)
In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that * No two adjacent vertices have the same color, and * The numbers of vertices in any two color classes differ by at most one.
| Property | Value |
|---|---|
| dbo:abstract | In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that * No two adjacent vertices have the same color, and * The numbers of vertices in any two color classes differ by at most one. That is, the partition of vertices among the different colors is as uniform as possible. For instance, giving each vertex a distinct color would be equitable, but would typically use many more colors than are necessary in an optimal equitable coloring. An equivalent way of defining an equitable coloring is that it is an embedding of the given graph as a subgraph of a Turán graph with the same set of vertices. There are two kinds of chromatic number associated with equitable coloring. The equitable chromatic number of a graph G is the smallest number k such that G has an equitable coloring with k colors. But G might not have equitable colorings for some larger numbers of colors; the equitable chromatic threshold of G is the smallest k such that G has equitable colorings for any number of colors greater than or equal to k. The Hajnal–Szemerédi theorem, posed as a conjecture by Paul Erdős and proven by András Hajnal and Endre Szemerédi, states that any graph with maximum degree Δ has an equitable coloring with Δ + 1 colors. Several related conjectures remain open. Polynomial time algorithms are also known for finding a coloring matching this bound, and for finding optimal colorings of special classes of graphs, but the more general problem of deciding whether an arbitrary graph has an equitable coloring with a given number of colors is NP-complete. (en) En mathématiques, et en particulier en théorie des graphes, une coloration équitable est l'opération qui consiste à affecter des couleurs aux sommets d'un graphe non orienté (coloration de graphe), de telle manière que : * deux sommets adjacents n'aient jamais la même couleur * les nombres de sommets dans les différentes couleurs ne diffèrent que de 1 au plus. En d'autres termes, la répartition des sommets en différentes couleurs doit être aussi uniforme que possible. La solution évidente pour obtenir une coloration équitable est de donner à chaque sommet une couleur différente. Néanmoins, cette solution emploie beaucoup plus de couleurs que nécessaire. La plupart du temps, on cherche à obtenir une coloration équitable optimale en minimisant le nombre de couleurs. (fr) Равномерная раскраска — это назначение цветов вершинам неориентированного графа таким образом, что: * Никакие две смежные вершины не имеют тот же самый цвет; * Число вершин в любых двух классах цветов отличаются не более чем на единицу. То есть, разбиение вершин на различные цвета настолько однородно, насколько это возможно. Например, задание каждой вершине различных цветов было бы равномерной раскраской, но, как правило, при этом будет использовано намного больше цветов, чем необходимо для оптимальной равномерной раскраски. Эквивалентный способ определения равномерной раскраски — это вложение заданного графа в качестве подграфа в граф Турана с тем же множеством вершин. Есть два вида хроматических чисел, ассоциированных с равномерной раскраской. Равномерное хроматическое число графа G — это наименьшее число k, такое что граф G имеет равномерную раскраску с k цветами. Однако граф G может не иметь равномерные раскраски для некоторых бо́льших наборов цветов. Равномерный хроматический порог графа G — это наименьшее число k, такое что граф G имеет равномерные раскраски для любого числа цветов, большего или равного k. Теорема Хайнала — Семереди, которую сформулировал как гипотезу Пал Эрдёш, а доказали Андраш Хайнал и Эндре Семереди, утверждает, что любой граф с максимальной степенью имеет равномерную раскраску с цветами. Несколько связанных гипотез остаются открытыми. Известны также алгоритмы полиномиального времени для поиска раскраски, соответствующей этой границе, а также алгоритмы поиска оптимальных раскрасок специальных классов графов, но более общая задача определения, имеет ли произвольный граф равномерную раскраску с заданным числом цветов NP-полна. (ru) Рівномірне розфарбування в теорії графів — це приписування кольорів вершинам неорієнтованого графа, таким чином, що * Ніякі дві суміжні вершини не мають однаковий колір, * Число вершин у будь-яких двох колірних класах відрізняються більш ніж на одиницю. Тобто, це процес розбиття вершин на різні кольори якомога більш рівномірним чином. Наприклад, для рівномірності слід давати кожній вершині свій власний колір, що призводить до того, що зазвичай, використовують набагато більше кольорів, ніж необхідно для оптимального розфарбування. Еквівалентний спосіб визначення рівномірного розфарбування є вкладенням даного графа як підграфа графа Турана. Є два види хроматичних чисел, які пов'язані з рівномірним розфарбуванням. Рівномірним хроматичним числом графа G називається найменше число k, при якому G має рівномірне розфарбування з k кольорів. Але G може не мати рівномірного розфарбування для деякого великого числа кольорів; рівномірний хроматичний поріг G є найменше число k, при якому G має рівномірне розфарбування для будь-якої кількості кольорів більшої або рівної k. Теорема Хайнала-Семереді, подається як гіпотеза Ердеша (1964) і доведена і Семереді (1970). Вона стверджує, що будь-який граф з максимальним степенем Δ має рівномірне розфарбування з Δ + 1 кольорів. Для знаходження розфарбування застосовуються алгоритми поліноміального часу, ці алгоритми використовуються також для знаходження оптимального розфарбування спеціальних класів графів, але є більш загальна проблема — чи має довільний граф NP-повне рівномірне розфарбування із заданою кількістю кольорів. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Equitable-K15.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.fceia.unr.edu.ar/~daniel/ecopt/index.html http://www.opuscula.agh.edu.pl/vol26/1/art/opuscula_math_2603.pdf http://www.ii.uib.no/~daniello/papers/COCOA-coloring.pdf http://portal.acm.org/citation.cfm%3Fid=365411.365811 |
| dbo:wikiPageID | 21796230 (xsd:integer) |
| dbo:wikiPageLength | 18724 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1041846384 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Job_Shop_Scheduling dbr:Dense_graph dbr:Undirected_graph dbr:Variance dbc:Graph_coloring dbr:Complete_bipartite_graph dbr:Complete_graph dbr:Chromatic_number dbr:Gabriel_Andrew_Dirac dbr:Glossary_of_graph_theory dbr:Graph_coloring dbr:NP-complete dbr:Opuscula_Mathematica dbr:Load_balancing_(computing) dbr:Star_(graph_theory) dbr:Clique_(graph_theory) dbr:Combinatorics,_Probability_and_Computing dbr:Complement_graph dbr:File:Equitable-K15.svg dbr:Acta_Mathematica_Hungarica dbr:Tree_(graph_theory) dbr:Treewidth dbr:American_Mathematical_Monthly dbr:Brooks'_theorem dbr:Outerplanar_graph dbr:Discrete_Mathematics_(journal) dbr:Graph_theory dbr:Journal_of_Combinatorial_Theory dbr:Hamiltonian_path dbr:Chernoff_bound dbr:Split_graph dbr:Graph_products dbr:Vertex_(graph_theory) dbr:Lovász_local_lemma dbr:Parameterized_complexity dbr:Turán_graph dbr:Erdős_conjecture |
| dbp:author1Link | András Hajnal (en) |
| dbp:author2Link | Endre Szemerédi (en) |
| dbp:authorlink | Paul Erdős (en) |
| dbp:first | Paul (en) Endre (en) András (en) |
| dbp:last | Hajnal (en) Szemerédi (en) Erdős (en) |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harvtxt dbt:Refbegin dbt:Refend dbt:Reflist dbt:Harvnb dbt:Harvs |
| dbp:year | 1964 (xsd:integer) 1970 (xsd:integer) |
| dcterms:subject | dbc:Graph_coloring |
| gold:hypernym | dbr:Assignment |
| rdfs:comment | In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that * No two adjacent vertices have the same color, and * The numbers of vertices in any two color classes differ by at most one. (en) En mathématiques, et en particulier en théorie des graphes, une coloration équitable est l'opération qui consiste à affecter des couleurs aux sommets d'un graphe non orienté (coloration de graphe), de telle manière que : * deux sommets adjacents n'aient jamais la même couleur * les nombres de sommets dans les différentes couleurs ne diffèrent que de 1 au plus. En d'autres termes, la répartition des sommets en différentes couleurs doit être aussi uniforme que possible. (fr) Равномерная раскраска — это назначение цветов вершинам неориентированного графа таким образом, что: * Никакие две смежные вершины не имеют тот же самый цвет; * Число вершин в любых двух классах цветов отличаются не более чем на единицу. (ru) Рівномірне розфарбування в теорії графів — це приписування кольорів вершинам неорієнтованого графа, таким чином, що * Ніякі дві суміжні вершини не мають однаковий колір, * Число вершин у будь-яких двох колірних класах відрізняються більш ніж на одиницю. (uk) |
| rdfs:label | Equitable coloring (en) Coloration équitable (fr) Равномерная раскраска (ru) Рівномірне розфарбування (uk) |
| owl:sameAs | freebase:Equitable coloring wikidata:Equitable coloring dbpedia-fr:Equitable coloring dbpedia-ru:Equitable coloring dbpedia-uk:Equitable coloring https://global.dbpedia.org/id/2mJGB |
| prov:wasDerivedFrom | wikipedia-en:Equitable_coloring?oldid=1041846384&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Equitable-K15.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Equitable_coloring |
| is dbo:wikiPageRedirects of | dbr:Hajnal-Szemeredi_theorem dbr:Hajnal–Szemerédi_theorem dbr:Equitable_colouring dbr:Equitable_chromatic_number dbr:Equitable_chromatic_threshold dbr:Hajnal-Szemerédi_theorem |
| is dbo:wikiPageWikiLink of | dbr:List_of_conjectures_by_Paul_Erdős dbr:Hajnal-Szemeredi_theorem dbr:Hajnal–Szemerédi_theorem dbr:András_Hajnal dbr:Graph_coloring dbr:Edge_coloring dbr:Equitable_colouring dbr:Brooks'_theorem dbr:Equitable_chromatic_number dbr:Equitable_chromatic_threshold dbr:Blow-up_lemma dbr:Turán_graph dbr:Hajnal-Szemerédi_theorem |
| is foaf:primaryTopic of | wikipedia-en:Equitable_coloring |
