You get a bonus - 1 coin for daily activity. Now you have 1 coin

Coloring graphs

Lecture




  Coloring graphs

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.

Content

  • 1. History
  • 2 Definition and terminology
    • 2.1 Vertex Coloring
    • 2.2 Chromatic polynomial
    • 2.3 Ribbed coloring
    • 2.4 Total coloring
  • 3 Properties
    • 3.1 Properties of chromatic polynomial
    • 3.2 Chromatic number limits
    • 3.3 Graphs with a large chromatic number
    • 3.4 Restrictions on chromatic index
    • 3.5 Other properties
    • 3.6 Open questions
  • 4 Algorithms coloring
    • 4.1 Polynomial algorithms
    • 4.2 Exact algorithms
    • 4.3 Compression
    • 4.4 Greedy coloring
    • 4.5 Parallel and Distributed Algorithms
    • 4.6 Decentralized Algorithms
    • 4.7 Computation Difficulty
  • 5 Application
    • 5.1 Planning
    • 5.2 Register allocation
    • 5.3 Digital watermarks
    • 5.4 Other uses
  • 6 Notes
  • 7 Sources

Story

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]

Definition and terminology

Vertex coloring

  Coloring graphs

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 graphs .

Coloring with   Coloring graphs flowers called   Coloring graphs painting . The smallest number of colors needed to color the graph   Coloring graphs called its chromatic number and is often written as   Coloring graphs . Sometimes used   Coloring graphs , since   Coloring graphs 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,   Coloring graphs The coloring is the same as dividing the vertices into   Coloring graphs independent sets. [one]

Chromatic polynomial [edit]

Main article: Chromatic number

Chromatic polynomial is a function   Coloring graphs which counts the number of t- colorings   Coloring graphs . From the name it follows that for given   Coloring graphs 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]

  Coloring graphs

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,   Coloring graphs , and of course,   Coloring graphs .

The chromatic polynomial contains at least as much colorization information.   Coloring graphs how much and chromatic number. Indeed,   Coloring graphs - the smallest positive integer that is not the root of the chromatic polynomial.

  Coloring graphs

Chromatic polynomials for some graphs
Triangular   Coloring graphs   Coloring graphs
Complete graph   Coloring graphs   Coloring graphs
Tree with   Coloring graphs ribs   Coloring graphs
Cycle   Coloring graphs   Coloring graphs
Count Petersen   Coloring graphs

Ribbed coloring

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   Coloring graphs - this is his chromatic index , or an edge chromatic number ,   Coloring graphs .

Total coloring

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   Coloring graphs count   Coloring graphs - This is the smallest number of colors needed for any full coloring.

Properties

Properties of the chromatic polynomial [edit]

  • If a   Coloring graphs - empty graph [9] ,

  Coloring graphs

  • If the graph   Coloring graphs - union of non-intersecting subgraphs   Coloring graphs and   Coloring graphs [9]

  Coloring graphs

  • If in   Coloring graphs there is a loop [9] ,

  Coloring graphs

Chromatic number limits

  • Assigning to all vertices of different colors always gives the correct coloring, so

  Coloring graphs

  • The only kind of graphs that can be colored in one color is zero graphs.
  • Complete graph   Coloring graphs , consisting of   Coloring graphs peaks require   Coloring graphs colors.
  • With optimal coloring, there must be at least one edge of   Coloring graphs graph edges between every two color classes, so [10]

  Coloring graphs

  • If a   Coloring graphs is a union of non-intersecting subgraphs   Coloring graphs and   Coloring graphs then

  Coloring graphs

  • If a   Coloring graphs 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:

  Coloring graphs

For interval graphs, this restriction is exact.

  • By the 4 color theorem, any flat graph can be colored with 4 colors.
  • 2-colored graphs are bipartite graphs, including trees.

Graph   Coloring graphs is bipartite if and only if it does not contain cycles of odd length. [9]

  • The greedy coloring shows that any graph can be colored by using one color more than its maximum vertex degree [10] ,

  Coloring graphs

  • Complete graphs have   Coloring graphs and   Coloring graphs , cycle graphs have   Coloring graphs and   Coloring graphs so that for them this limitation is the best; in all other cases, the limitation can be improved; Brooks's theorem [11] states that

Brooks theorem:   Coloring graphs for a connected, simple graph   Coloring graphs , if a   Coloring graphs is neither a complete graph, nor a cycle graph.

Graphs with a large chromatic number [edit]

  • Graphs with large cliques have a large chromatic number, but the opposite is not always true. The Grötz graph is an example of a 4-colorable graph without triangles, and this example can be generalized to Mytzelsky graph.

Myzelsky theorem (Alexander Zykov 1949, Jan Mycielski 1955): There are graphs without triangles with arbitrarily large chromatic numbers.

  • From the Brooks theorem, graphs with a large chromatic number should have a high maximum degree of apex. Another local condition, due to which the chromatic number can be large is the presence of a large clique. But the colorability of a graph depends not only on local conditions: a graph with a large grip locally looks like a tree, so all the cycles are long, but its chromatic number is not 2:

Erdos theorem : There are graphs with arbitrarily large girth and chromatic number. [ten]

Chromatic Index Restrictions

  • Edge Coloring   Coloring graphs is the coloring of the vertices of its linear graph   Coloring graphs , and vice versa. I.e,

  Coloring graphs

  • Moreover [12] ,

König theorem:   Coloring graphs , if a   Coloring graphs - dicotyledonous.

  • In general, the connection is much stronger than the Brooks theorem gives for coloring vertices [12] :

Vizing's Theorem: A graph with a maximum degree of vertex   Coloring graphs has an edge chromatic number   Coloring graphs or   Coloring graphs .

Other properties

  • A graph is k- chromatic if and only if it has an acyclic orientation, for which the length of the longest path is equal to k . This was proved in the Gallai-Hasse-Roy-Witaver theorem. [13]
  • For flat graphs, the coloring of the vertices is equivalent to an everywhere non-zero flow.
  • Much less is known about infinite graphs. Below are two results for coloring infinite graphs.
  1. If all finite subgraphs of an infinite graph   Coloring graphs k is chromatic, then   Coloring graphs is also k -chromatic, under the assumption of the axiom of choice. This is the formulation of the de Brain – Erdush theorem. [14]
  2. If the graph allows full n- coloring for any   Coloring graphs , then it admits an infinite full coloring. [15]

Open questions

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   Coloring graphs polynomial   Coloring graphs has no zeros in the area   Coloring graphs . Although it is known that such a chromatic polynomial does not have zeros in the region   Coloring graphs , So what   Coloring graphs , 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.

Coloring Algorithms

Polynomial algorithms

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.

Exact algorithms

The brute-force algorithm for the k-coloring case considers all   Coloring graphs combinations of arrangement of flowers in a graph with n vertices and checks them for correctness. Чтобы вычислить хроматическое число и хроматический полином данный алгоритм рассматривает каждое k, и может работать эффективно только для небольших графов.

Используя динамическое программирование и оценку размера наибольшего независимого множества в графе возможность k-раскраски может быть разрешена за время   Coloring graphs [16] . Известны более быстрые алгоритмы для 3- и 4-раскрасок, сходящиеся за время   Coloring graphs [17] и   Coloring graphs [18] соответственно.

Сжатие

Сжатие   Coloring graphs графа   Coloring graphs — это граф, полученный отождествлением вершин   Coloring graphs and   Coloring graphs , удаление соединяющих их ребер, замена на одну вершину   Coloring graphs , куда перенаправляются ребра инцидентные вершинам   Coloring graphs and   Coloring graphs . Эта операция играет важную роль в анализе раскраски графов.

Хроматическое число удовлетворяет рекуррентному соотношению:

  Coloring graphs ,

Where   Coloring graphs and   Coloring graphs несмежные вершины,   Coloring graphs граф с добавленным ребром   Coloring graphs . Некоторые алгоритмы основаны на данном соотношении, выдавая как результат дерево, иногда называемое деревом Зыкова. Время выполнения зависит от метода выбора вершин   Coloring graphs and   Coloring graphs .

Хроматический полином удовлетворяет рекуррентному соотношению:

  Coloring graphs ,

Where   Coloring graphs and   Coloring graphs смежные вершины,   Coloring graphs граф с удалением ребра   Coloring graphs .   Coloring graphs представляет собой число возможных правильных раскрасок графа, когда вершины могут иметь одинаковые или различные цвета. If a   Coloring graphs and   Coloring graphs имеют разные цвета, тогда мы можем рассмотреть граф, где   Coloring graphs and   Coloring graphs смежные. If a   Coloring graphs and   Coloring graphs имеют одинаковые цвета, мы можем рассмотреть граф, где   Coloring graphs and   Coloring graphs объединены.

Выражения данные выше приводят к рекурсивной процедуре, названной алгоритм удаления-сжатия , сформировавшей основу для многих алгоритмов раскраски графов. Время работы удовлетворяет такому же рекуррентному соотношению, как и числа Фибоначчи, поэтому в наихудшем случае алгоритм будет работать за время   Coloring graphs для n вершин и m ребер. [19] На практике, метод ветвей и границ и отбрасывание изоморфных графов позволяет избежать некоторых рекурсивных вызовов, время работы зависит от метода подбора пары вершин.

Жадная раскраска

  Coloring graphs

Два результата работы жадного алгоритма при выборе разных порядков вершин.

Жадный алгоритм упорядочивает вершины   Coloring graphs , ...,   Coloring graphs и последовательно присваивает вершине   Coloring graphs наименьший доступный цвет, не использовавшийся для окраски соседей   Coloring graphs среди   Coloring graphs , ...,   Coloring graphs , либо добавляет новый. Качество полученной раскраски зависит от выбранного порядка. Всегда существует такой порядок, который приводит жадный алгоритм к оптимальному числу   Coloring graphs красок. С другой стороны, жадный алгоритм может быть сколь угодно плохим; например, корона с n вершинами может быть раскрашена 2 цветами, а упорядочивание может привести к числу цветов равному   Coloring graphs .

Для хордального графа и для его особых случаев(например, интервальный граф) алгоритм жадной раскраски может быть использован для нахождения оптимальной раскраски за полиномиальное время, выбирая порядок вершин обратным ксовершенному порядку исключения. Однако найти такой порядок — NP-сложная задача для данного графа.

Если вершины упорядочены в соответствии с их степенями, алгоритм жадной раскраски использует не более чем   Coloring graphs цветов, как максимум на 1 больше чем   Coloring graphs (   Coloring graphs — степень вершины   Coloring graphs ). Этот эвристический алгоритминогда называют алгоритмом Уэлша-Пауэлла. [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   Coloring graphs 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  Coloring graphs .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,  Coloring graphs . The more colors are used (   Coloring graphs instead   Coloring graphs ), 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 graphs coloring requires   Coloring graphs 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   Coloring graphs in one synchronous step of communication. Repeating the same procedure, we can obtain the 3-coloring of the n- cycle for   Coloring graphs communication rounds (provided we have unique node identifiers).

Function   Coloring graphs , 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   Coloring graphs 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   Coloring graphs . [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 graphs coloring for   Coloring graphs 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

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] .

Computational complexity

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   Coloring graphs 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]

Application

Planning

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.

Register allocation

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 watermarks

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   Coloring graphs , 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] .

Other uses

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
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Discrete Math. Set theory. Graph theory. Combinatorics.

Terms: Discrete Math. Set theory. Graph theory. Combinatorics.