Lecture
Correct coloring of graph vertices by the smallest set of colors - three.
In graph theory, the coloring of graphs is a special case of graph marking. When coloring, the elements of the graph correspond to the labels, subject to certain restrictions; these labels are traditionally called “flowers”. In the simplest case, this method of coloring the vertices of the graph, in which different colors correspond to any two adjacent vertices, is called vertex coloring . Similarly, the coloring of the edges assigns a color to each edge so that any two adjacent edges have different colors. [1] Finally, the coloring of areas of a planar graph designates the color of each area, so that every two areas that have a common border cannot have the same color.
The coloring of the vertices is the main problem of coloring the graphs, all other tasks in this area can be transferred to this model. For example, the coloring of the edges of a graph is the coloring of the vertices of its edge graph, and the coloring of the areas of a planar graph is the coloring of the vertices of the dual graph. [1] However, other problems coloring graphs are often posed and solved in the original formulation. The reason for this is partly because it gives a better idea of what is happening and is more revealing, and partly because it is more convenient to solve some tasks in this way (for example, coloring edges).
The agreement on the use of colors comes from the tradition of highlighting countries on the political map. It was generalized to the color of the planar graph areas. Through dual graphs, this model spread to the coloring of the vertices, and then to other types of graphs. In mathematical and computer representation, usually non-negative integers (from zero and more) are used as colors. Thus, we can use any final set as a “color set”, and the problem of coloring graphs depends on the number of colors, not on what they are.
Coloring graphs is used in many practical areas, not only in theoretical problems. In addition to the classic types of problems, various restrictions may also be imposed on the graph, on the method of assigning colors or on the colors themselves. This method, for example, is used in the popular Shoudoku puzzle. Active research is still underway in this area.
Note: Many of the terms given in this article are defined in the Glossary of Graph Theory.
The first results were obtained for flat graphs in the problem of coloring maps. Trying to color the map of the districts of England, Francis Guthrie formulated the problem of four colors, noting that four colors are enough to color the map so that any two adjacent regions have different colors. His brother referred the question to his math teacher, Augustus de Morgan, who mentioned it in his letter to William Hamilton in 1852. Arthur Cayley raised this issue at a meeting in London in 1878. In the same year, Tate proposed the first solution to this problem. He reduced the coloring of the vertices of the original graph to the coloring of the edges of the dual graph and suggested that this problem always has a solution. [2] In 1880, Alfred Kempe published a paper stating that he was able to establish the result, and the problem of four colors was considered solved for a decade. For this achievement, Kempe was elected a member of the Royal Society of London and later - President of the London Mathematical Society. [3]
In 1890, Hivud noted that the arguments cited by Kempe were incorrect. However, in this article he proved the five-color theorem, showing that any flat map can be painted with no more than five colors. However, he relied on the ideas of Kempe. In the next century, a large number of theories were developed in an attempt to reduce the minimum number of colors. The four-color theorem was finally proved in 1977 by scientists Kenneth Appel and Wolfgang Hacken. The idea of the proof was largely based on the ideas of Hewood and Kempe and ignored most of the intermediate studies. [4] The proof of the four-color theorem is one of the first proofs in which a computer was used.
In 1912, George David Birkhoff proposed using a chromatic polynomial to study coloring problems, which he generalized to the Tutta polynomial, which is an important part in algebraic graph theory. Kempe in 1879 already paid attention to the general case when the graph was not flat. [5] Many results of generalizations of coloring of flat graphs on surfaces of higher orders appeared at the beginning of the 20th century.
In 1960, Claude Berge formulated another idea about the coloring of graphs, the statement about perfect graphs , motivated by the information-theoretical concept, called the zero error of the capacity of the graph, presented by Shannon. The statement remained unconfirmed for 40 years, until it was proved as the famous theorem on perfect graphs by mathematicians Chudnovskaya, Robertson, Seymour and Thomas in 2002.
The coloring of graphs began to be studied as an algorithmic problem from the 1970s: the definition of the chromatic number is one of 21 NP-complete Karp problems since 1972. And at about the same time, various algorithms were developed based on a search with a return and recursive removal-compression of Zykov. [6] Since 1981, the coloring of the graph has been used to allocate registers in compilers. [7]
This graph can be colored in 3 colors in 12 ways.
When they talk about coloring graphs, they almost always mean by this the coloring of their vertices, that is, the assignment of color labels to the vertices of the graph so that any two vertices that have a common edge have different colors. Since the graphs in which there are loops can not be colored in this way, they are not the subject of discussion.
The terminology in which labels are called colors comes from the coloring of political maps. Labels such as red or blue are used only when the number of colors is small, but usually it is assumed that labels are integers. 
.
Coloring with 
flowers called painting . The smallest number of colors needed to color the graph 
called its chromatic number and is often written as 
. Sometimes used 
, since denotes the Euler characteristic. A subset of the vertices in one color is called a color class , each such class forms an independent set. In this way, The coloring is the same as dividing the vertices into independent sets. [one]
Main article: Chromatic number
Chromatic polynomial is a function 
which counts the number of t- colorings . From the name it follows that for given this function is a polynomial dependent on t . This fact was discovered by Birkhoff and Lewis while trying to prove the four color hypothesis. [eight]
All non-isomorphic graphs from 3 vertices and their chromatic polynomials. The empty graph E 3 (red) allows coloring in one color, the others are not. A green graph can be colored in 3 colors in 12 ways.
For example, the graph in the image on the right can be colored in 12 ways using 3 colors. Two colors it can not be painted in principle. Using 4 colors, we get 24 + 4 * 12 = 72 coloring options: when using all 4 colors, there are 4! = 24 correct ways ( each assignment of 4 colors for any graph of 4 vertices is correct); and for every 3 colors of these 4 there are 12 coloring methods. Then, for the graph in the example, the table of numbers of correct colorings will start like this:
| Available number of colors | one | 2 | 3 | four | ... |
| The number of ways to paint | 0 | 0 | 12 | 72 | ... |
For the graph in the example, 
, and of course, 
.
The chromatic polynomial contains at least as much colorization information. how much and chromatic number. Indeed, 
- the smallest positive integer that is not the root of the chromatic polynomial.
Triangular  |
 |
Complete graph  |
 |
Tree with  ribs |
 |
Cycle  |
 |
| Count Petersen |  |
Main article: Ribbed coloring
The edge coloring of a graph implies the assignment of colors to edges so that no two edges of the same color belong to the same vertex. This task is equivalent to dividing the set of faces into sets of independent faces. The smallest number of colors needed for the graph's edge coloring - this is his chromatic index , or an edge chromatic number , 
.
Main article: Total coloring
Total coloring is one of the types of coloring of the vertices and edges of the graph. Under it implies such an assignment of colors that neither adjacent vertices, nor adjacent edges, nor vertices and edges that connect them, do not have the same color. Full chromatic number 
count - This is the smallest number of colors needed for any full coloring.
- empty graph [9] ,
- union of non-intersecting subgraphs 
and 
[9]
there is a loop [9] ,
, consisting of peaks require 
colors.
graph edges between every two color classes, so [10]
is a union of non-intersecting subgraphs and then
contains clicks of size k , then at least k colors are needed to color this click, in other words the chromatic number is greater than or equal to the dimension of the click:
For interval graphs, this restriction is exact.
Graph is bipartite if and only if it does not contain cycles of odd length. [9]
and 
, cycle graphs have 
and 
so that for them this limitation is the best; in all other cases, the limitation can be improved; Brooks's theorem [11] states thatBrooks theorem: 
for a connected, simple graph , if a is neither a complete graph, nor a cycle graph.
Myzelsky theorem (Alexander Zykov 1949, Jan Mycielski 1955): There are graphs without triangles with arbitrarily large chromatic numbers.
Erdos theorem : There are graphs with arbitrarily large girth and chromatic number. [ten]
is the coloring of the vertices of its linear graph 
, and vice versa. I.e,
König theorem: 
, if a - dicotyledonous.
Vizing's Theorem: A graph with a maximum degree of vertex 
has an edge chromatic number or 
.
k is chromatic, then is also k -chromatic, under the assumption of the axiom of choice. This is the formulation of the de Brain – Erdush theorem. [14]
, then it admits an infinite full coloring. [15]The chromatic number of the plane in which the two points are adjacent if the unit distance between them is unknown. It can be 4, 5, 6, or 7. Other open questions about the chromatic number of graphs include the Hardwiger hypothesis, stating that any graph with chromatic number k has a complete graph of k vertices, like its minor, the Erdush – Faber Hypothesis –Lovasa, which limits the chromatic number of complete graphs that have exactly one common vertex for each pair of graphs, and the Albertson hypothesis that among the k -chromatic graphs, those that have the least number of intersections are complete.
When Birkov and Lewis introduced the chromatic polynomial in their attempt to solve the four-color theorem, they argued that for flat graphs polynomial has no zeros in the area 
. Although it is known that such a chromatic polynomial does not have zeros in the region 
, So what 
, their assertion remains unproven. It also remains an open question how to distinguish graphs with the same chromatic polynomial, and how to determine that the polynomial is chromatic.
For a bipartite graph, the coloring problem is computed in linear time using a wide search. In the case of perfect graphs, the chromatic number and the corresponding coloring can be found in polynomial time using semi-defined programming. Approximate formulas for finding the chromatic number are known for many classes of graphs (forests, cycles, wheels, chordal graphs) and can also be calculated in polynomial time.
The brute-force algorithm for the k-coloring case considers all 
combinations of arrangement of flowers in a graph with n vertices and checks them for correctness. Чтобы вычислить хроматическое число и хроматический полином данный алгоритм рассматривает каждое k, и может работать эффективно только для небольших графов.
Используя динамическое программирование и оценку размера наибольшего независимого множества в графе возможность k-раскраски может быть разрешена за время 
[16] . Известны более быстрые алгоритмы для 3- и 4-раскрасок, сходящиеся за время 
[17] и 
[18] соответственно.
Сжатие 
графа — это граф, полученный отождествлением вершин 
and 
, удаление соединяющих их ребер, замена на одну вершину 
, куда перенаправляются ребра инцидентные вершинам and . Эта операция играет важную роль в анализе раскраски графов.
Хроматическое число удовлетворяет рекуррентному соотношению:
,
Where and несмежные вершины, 
граф с добавленным ребром 
. Некоторые алгоритмы основаны на данном соотношении, выдавая как результат дерево, иногда называемое деревом Зыкова. Время выполнения зависит от метода выбора вершин and .
Хроматический полином удовлетворяет рекуррентному соотношению:
,
Where and смежные вершины, 
граф с удалением ребра . 
представляет собой число возможных правильных раскрасок графа, когда вершины могут иметь одинаковые или различные цвета. If a and имеют разные цвета, тогда мы можем рассмотреть граф, где and смежные. If a and имеют одинаковые цвета, мы можем рассмотреть граф, где and объединены.
Выражения данные выше приводят к рекурсивной процедуре, названной алгоритм удаления-сжатия , сформировавшей основу для многих алгоритмов раскраски графов. Время работы удовлетворяет такому же рекуррентному соотношению, как и числа Фибоначчи, поэтому в наихудшем случае алгоритм будет работать за время 
для n вершин и m ребер. [19] На практике, метод ветвей и границ и отбрасывание изоморфных графов позволяет избежать некоторых рекурсивных вызовов, время работы зависит от метода подбора пары вершин.
Два результата работы жадного алгоритма при выборе разных порядков вершин.
Жадный алгоритм упорядочивает вершины 
, ..., 
и последовательно присваивает вершине 
наименьший доступный цвет, не использовавшийся для окраски соседей среди , ..., 
, либо добавляет новый. Качество полученной раскраски зависит от выбранного порядка. Всегда существует такой порядок, который приводит жадный алгоритм к оптимальному числу красок. С другой стороны, жадный алгоритм может быть сколь угодно плохим; например, корона с n вершинами может быть раскрашена 2 цветами, а упорядочивание может привести к числу цветов равному 
.
Для хордального графа и для его особых случаев(например, интервальный граф) алгоритм жадной раскраски может быть использован для нахождения оптимальной раскраски за полиномиальное время, выбирая порядок вершин обратным ксовершенному порядку исключения. Однако найти такой порядок — NP-сложная задача для данного графа.
Если вершины упорядочены в соответствии с их степенями, алгоритм жадной раскраски использует не более чем 
цветов, как максимум на 1 больше чем ( 
— степень вершины ). Этот эвристический алгоритминогда называют алгоритмом Уэлша-Пауэлла. [20] Другой алгоритм устанавливает порядок динамично, выбирая следующую вершину той, которая имеет наибольшее число смежных вершин разных цветов. Многие другие алгоритмы раскраски графов основаны на жадной раскраске и используют статические или динамические стратегии выбора порядка вершин.
In the field of distributed algorithms, the coloring of graphs is closely related to the problem of symmetry breaking. With a sufficiently large maximum degree of vertices, the most developed probabilistic algorithms operate faster than deterministic algorithms. The fastest probabilistic algorithms use the technique of multiple attempts. [21]
In symmetric graphs, deterministic distributed algorithms cannot determine the color of the vertex. Additional information is needed to avoid symmetry. A standard assumption is made that initially each vertex has a unique identifier, for example, from the set
.Let's go from the reverse, assuming that we are given an n- coloring. The challenge is to reduce the number of colors from n to, for example,
. The more colors are used ( 
instead ), the fewer communication rounds are required. A communication round involves exchanging a node with an arbitrary message with one of its neighbors. [21]
A simple version of a distributed greedy algorithm for coloring requires 
communication rounds in the worst case — information may have to be passed from one side of the network to the other.
The simplest interesting case is the n- cycle. Richard Cole and Uzi Vishkin [22] show that there is a distributed algorithm that reduces the number of colors from n to 
in one synchronous step of communication. Repeating the same procedure, we can obtain the 3-coloring of the n- cycle for 
communication rounds (provided we have unique node identifiers).
Function 
, repeated logarithm, is an extremely slow growing function, "almost constant." Consequently, the results of Cole and Vishkin raise the question of whether there is a distributed n-cycle 3-coloring algorithm that runs in constant time. Nathan Lineal showed that this is not possible: any deterministic distributed algorithm requires 
communication rounds to reduce N -coloring to 3-coloring in the n-cycle. [23]
The Cole and Vishkin techniques can also be applied to an arbitrary graph with a limited degree of vertices, in which case the running time is 
. [24] This method was generalized for the graph of unit circles by Schneider et al. [25]
The problem of coloring the edges was also studied in a distributed model. Pansonezzi and Rizzi reached 
coloring for 
in this model. [26] The lower limit for the distributed coloring of the vertices achieved by Lineial is also applicable to the problem of distributed coloring of edges. [27]
Decentralized algorithms are those in which internal messaging is not allowed (as opposed to distributed algorithms, where processes exchange data with each other). There are effective decentralized algorithms that successfully cope with the task of coloring graphs. These algorithms work on the assumption that the vertex is able to "feel" that any of its neighboring vertices is painted in the same color as it. In other words, it is possible to determine a local conflict. Such a condition is quite often performed in real applications - for example, when transmitting data over a wireless channel, a transmitting station, as a rule, has the ability to detect what the other station is trying to transmit simultaneously to the same channel. The ability to obtain such information is a sufficient condition that the algorithms based on the learning automata with a single probability correctly solve the problem of coloring the graph [28] [29] .
Coloring a graph is computationally challenging. It is considered that finding out whether a graph admits a k-coloring for a given k is an NP-complete problem, except for the cases k = 1 and k = 2. In particular, the problem of calculating the chromatic number of NP-complex. [30] The 3-coloring problem is NP-complete even for the case of a planar graph of degree 4. [31]
Also, an NP-challenge is the coloring of a 3-colored graph with 4 colors [32] and a k- colored graph 
for sufficiently large values of k . [33]
Calculating the chromatic polynomial coefficients # P complex task. At present, there is not a single FPRAS for calculating the chromatic polynomial for any rational number k ≥ 1.5, except for k = 2, unless it is satisfied that NP = RP. [34]
Coloring vertices models many planning problems. [35] In its simplest setting, a given set of works should be distributed over time intervals, each such work takes one segment. They can be performed in any order, but two jobs may conflict in the sense that they cannot be performed simultaneously, since, for example, they share resources. The corresponding graph contains a vertex for each of the jobs and a face for each conflicting pair. The chromatic number of the constructed graph is the minimum execution time for all jobs without conflicts.
Details of the planning problem determine the structure of the graph. For example, when airplanes are distributed among flights, the resulting conflict graph is an interval graph, so the coloring problem can be solved effectively. When allocating radio frequencies, a single disk graph is obtained conflicts, and the problem is solved using 3 colors.
Main article: Register allocation
A compiler is a computer program that translates one computer language into another. To improve the execution time of the resulting code, one of the techniques of compiler optimization is register allocation, in which the most frequently used variables of the compiled program are stored in high-speed registers of the processor. In the ideal case, variables are stored in registers so that they are all in registers during their use.
One approach to this problem is to transfer it to the graph coloring model. The compiler builds an interference graph , where the vertices correspond to the registers, and the face connects two of them, if they are needed at the same time. If this graph is k- chromatic, then variables can be stored in k registers.
Digital watermarking technology (English digital watermarking ) allows along with data (whether it be media files, executable files, and others) to transmit some hidden message ("watermark", Watermark ). Such a hidden message can be used in copyright protection to identify the owner of the data.
This is important, for example, to determine the source of their distribution in an illegal manner. Or to confirm the rights to the data, for example - software systems on a chip ( system-on-chip ).
The message can be encoded including in the column. One of these techniques was proposed by Qu and Potkonjak (therefore, it is sometimes called the QP algorithm) in [37] .
It consists of this: let's say we have a graph , the coloring of which is used in the program - moreover, it is used in such a way that it is permissible to change the contents of the graph with a small increase in its chromatic number. What is important, one of such examples is the incompatibility graph (interference graph) of the distribution of the registers of the processor, which was mentioned above, which means that we will be able to encode the message in a software product using the distribution of registers.
You can extract it by comparing the resulting graph with the original one; there are also ways to ascertain whether a message was encoded in the graph without using the original one — the extraction is described in more detail, for example, in [38] .
The development and refinement of the thoughts of Qu and Potkonjak , attempts to improve the algorithm occur in [39] , [40] , [38] .
The task of coloring graphs has been set in many other areas of application, including comparison with a template.
Solving the Sudoku puzzle can be seen as the completion of the coloring with 9 colors of a given graph of 81 vertices.
Comments
To leave a comment
Discrete Math. Set theory. Graph theory. Combinatorics.
Terms: Discrete Math. Set theory. Graph theory. Combinatorics.