| The smallest number of colors needed for an edge coloring of a graph G is the chromatic index, or edge chromatic number, χ'(G). | Наименьшее число цветов, необходимое для рёберной раскраски графа G {\displaystyle G} - это его хроматический индекс, или рёберное хроматическое число, χ' (G) {\displaystyle \chi '(G)}. |
| The line graphs of bipartite graphs are perfect: in them, and in any of their induced subgraphs, the number of colors needed in any vertex coloring is the same as the number of vertices in the largest complete subgraph. | Рёберные графы двудольных графов совершенны - в нём и в любом его порождённом подграфе число цветов, необходимых для любой раскраски вершин, равно числу вершин в наибольшей клике. |
| The Hadwiger conjecture states that the Hadwiger number is always at least as large as the chromatic number of G. That is, every graph with Hadwiger number k should have a graph coloring with at most k colors. | Гипотеза Хадвигера утверждает, что число Хадвигера всегда не меньше хроматического числа графа G. То есть любой граф с числом Хадвигера k должен бы иметь раскраску в максимум k цветов. |
| Any such chain can be recolored, preserving the validity of the coloring, by swapping its two colors on all vertices of the chain. | Любая такая цепь может быть перекрашена с сохранением допустимости раскраски путём обмена двух цветов на всех вершинах цепочки. |
| This auxiliary graph is 1-planar, from which it follows that Ringel's vertex-face coloring problem may also be solved with six colors. | Вспомогательный граф является 1-планарным, откуда следует, что задача Рингеля раскраски вершин и граней может быть решена с использованием шести цветов. |
| Thus, the Erdős-Faber-Lovász conjecture is equivalent to the statement that any simple hypergraph with n vertices has chromatic index (edge coloring number) at most n. | Таким образом, гипотеза Эрдёша - Фабера - Ловаса эквивалентна утверждению, что любой простой гиперграф с n вершинами имеет хроматический индекс (число цветов рёберной раскраски), не превосходящий n. |
| The Petersen graph requires at least three colors in any (possibly improper) coloring that breaks all of its symmetries; that is, its distinguishing number is three. | Граф Петерсена требует по меньшей мере трёх цветов в любой (возможно, несобственной) раскраске, которая нарушает все симметрии. |
| In graph theory, the Heawood conjecture or Ringel-Youngs theorem gives a lower bound for the number of colors that are necessary for graph coloring on a surface of a given genus. | Гипотеза Хивуда, или теорема Рингеля - Янгса даёт нижнюю границу для числа цветов, которые необходимы для раскраски графа на поверхности с заданным родом. |
| Thus, like the simpler Moser spindle, it provides a lower bound for the Hadwiger-Nelson problem: coloring the points of the Euclidean plane so that each unit line segment has differently-colored endpoints requires at least four colors. | Таким образом, подобно более простому веретену Мозера, граф даёт нижнюю границу для задачи Нелсона - Эрдёша - Хадвигера - раскраска точек евклидовой плоскости, так что единичный отрезок имеет различные цвета на концах, требует по меньшей мере четырёх цветов. |
| A greedy coloring algorithm that considers the edges of a graph or multigraph one by one, assigning each edge the first available color, may sometimes use as many as 2Δ - 1 colors, which may be nearly twice as many number of colors as is necessary. | Алгоритм жадной раскраски, выбирающий последовательно рёбра графа или мультиграфа и назначающий первый допустимый цвет, может иногда использовать 2 Δ - 1 {\displaystyle 2{\Delta}-1} цветов, что может почти вдвое превосходить необходимое число цветов. |
| In this story, each game represents an edge of O6, each weekday is represented by a color, and a 6-color edge coloring of O6 provides a solution to the players' scheduling problem. | В этой истории каждая игра представляет ребро O6, все дни представлены цветами, а рёберная раскраска в 6 цветов графа O6 даёт расписание. |
| It has been conjectured (combining Vizing's theorem and Brooks' theorem) that any graph has a total coloring in which the number of colors is at most the maximum degree plus two, but this remains unproven. | Существует гипотеза (комбинирующая теорему Визинга и теорему Брукса), что любой граф имеет тотальную раскраску, в которой число цветов не превосходит максимальной степени плюс два. |
| A 3-coloring may be found in linear time by a greedy coloring algorithm that removes any vertex of degree at most two, colors the remaining graph recursively, and then adds back the removed vertex with a color different from the colors of its two neighbors. | Раскраска тремя цветами может быть найдена за линейное время алгоритмом жадной раскраски, который удаляет любую вершину со степенью, не превосходящей двух и раскрашивает оставшийся граф рекурсивно, а затем возвращает каждую из удалённых вершин с цветом, отличным от цветов двух её соседей. |
| The arboricity of a graph is the minimum number of colors required so that the edges of each color have no cycles (rather than, in the standard edge coloring problem, having no adjacent pairs of edges). | Древесность графа - это минимальное число цветов, необходимых для раскраски таким образом, что рёбра любого цвета не содержат циклов (а не как в стандартной задаче раскраски - рёбра одного цвета несмежны). |
| Since circle graph coloring with four or more colors is NP-hard, and since any circle graph can be formed in this way from some book embedding problem, it follows that optimal book embedding is also NP-hard. | Поскольку раскраска кругового графа в четыре и более цветов является NP-трудной задачей, и поскольку любой круговой граф может быть образован таким образом из некоторой задачи нахождения книжного вложения, нахождение оптимального книжного вложения является также NP-трудной задачей. |
| A coloring with the number of colors described by Brooks' theorem is sometimes called a Brooks coloring or a Δ-coloring. | Раскраска с использованием числа цветов, указанной в теореме Брукса иногда называется раскраской Брукса, или Δ-раскраской. |
| Equivalently, a complete coloring is minimal in the sense that it cannot be transformed into a proper coloring with fewer colors by merging pairs of color classes. | Эквивалентно, полная раскраска - это минимальная раскраска, в том смысле, что её нельзя преобразовать в правильную раскраску с меньшим числом цветов путём слияния двух цветов. |
| Note that any coloring of a graph with the minimum number of colors must be a complete coloring, so minimizing the number of colors in a complete coloring is just a restatement of the standard graph coloring problem. | Заметим, что любая раскраска графа с минимальным числом цветов должна быть полной раскраской, так что минимизация числа цветов полной раскраски является просто переформулировкой стандартной задачи раскраски графа. |
| In particular, any graph has an equitable edge coloring, an edge coloring with an optimal number of colors in which every two color classes differ in size by at most one unit. | В частности, любой граф имеет справедливую рёберную раскраску, рёберную раскраску с оптимальным числом цветов, в которой два класса цветов по размеру отличаются максимум на единицу. |
| The Hajnal-Szemerédi theorem on equitable coloring states that any graph has a (Δ + 1)-coloring in which the sizes of any two color classes differ by at most one. | Теорема Хайналя - Семереди о равномерной раскраске утверждает, что любой граф имеет (Δ + 1)-цветную раскраску, при которой число вершин двух различных цветов отличается максимум на единицу. |
| The acyclic chromatic number A(G) of a graph G is the least number of colors needed in any acyclic coloring of G. Acyclic coloring is often associated with graphs embedded on non-plane surfaces. | Ациклическим хроматическим числом A(G) графа G называется наименьшее число цветов, необходимое в любой ациклической раскраске G. Ациклическая раскраска часто связывается с графами на поверхностях, не являющихся плоскостями. |
| For instance, complete edge coloring is the edge-coloring variant of complete coloring, a proper edge coloring in which each pair of colors must be represented by at least one pair of adjacent edges and in which the goal is to maximize the total number of colors. | Например, задача о полной рёберной раскраске является вариантом полной раскраски, правильной раскраски вершин, при которой любая пара цветов должна присутствовать хотя бы раз в множестве сопряжённых вершин, и задача состоит в максимизации общего числа цветов. |
| Because edge coloring is NP-complete even for three colors, it is unlikely to be fixed parameter tractable when parametrized by the number of colors. | Поскольку задача рёберной раскраски является NP-полной даже для трёх цветов, вряд ли она поддаётся фиксированной параметризации по числу цветов. |