Clever Geek Handbook
📜 ⬆️ ⬇️

Uniform coloring

Uniform coloring is the assignment of colors to the vertices of an undirected graph in such a way that

  • No two adjacent vertices have the same color
  • The number of vertices in any two color classes differs by no more than one.

That is, breaking the vertices into different colors is as uniform as possible. For example, assigning different colors to each vertex would be uniform coloring, but as a rule, a lot more colors would be used than is necessary for optimal uniform coloring. An equivalent way to determine uniform coloring is to embed a given graph as a subgraph in a Turan graph with the same set of vertices. There are two types of chromatic numbers associated with uniform coloring [1] . The uniform chromatic number of graph G is the smallest number k such that graph G has uniform coloring with k colors. However, the graph G may not have uniform coloring for some larger sets of colors. The uniform chromatic threshold of the graph G is the smallest number k such that the graph G has uniform coloring for any number of colors greater than or equal to k . [2]

The Hajnal – Szemerédi theorem , which was formulated as the Pal Erdös hypothesis [3] , and proved by András Hajnal and Endre Szemerédi [4] , states that any graph with a maximum degreeΔ {\ displaystyle \ Delta} \ Delta has uniform coloring withΔ+one {\ displaystyle \ Delta +1} \ Delta +1 flowers. Several related hypotheses remain open. Polynomial time algorithms for finding a coloring corresponding to this boundary are also known [5] , as well as algorithms for finding optimal colorings of special classes of graphs, but the more general problem of determining whether an arbitrary graph has a uniform coloring with a given number of colors is NP-complete .

Examples

 
Uniform coloring of the star K 1.5 .

The star K 1.5 shown in the figure is a complete bipartite graph , and therefore can be colored in two colors. However, the resulting coloring has one vertex of one color and five vertices of a different color, and therefore the coloring is not uniform. The smallest number of colors in the uniform coloring of this graph is four, as shown in the figure - the central vertex must belong to a class with a single vertex, so the remaining five vertices must be divided into at least three colors so that each class contains no more than two vertices. More generally, Meyer [6] noted that any star K 1, n requiresone+⌈n/2⌉ {\ displaystyle \ scriptstyle 1+ \ lceil n / 2 \ rceil}   colors for uniform coloring, and therefore the chromatic number of a graph can differ from its chromatic uniform number by no more than n / 4 times. Since K 1.5 has a maximum degree of five, the number of colors guaranteed by the Hajnal-Szemeredi theorem is six, which is obtained by assigning each vertex a different color.

Another interesting phenomenon is shown by another complete bipartite graph,K2n+one,2n+one {\ displaystyle K_ {2n + 1,2n + 1}}   . This graph has a uniform 2-coloring defined by its bipartite. However, it does not have a uniform (2 n + 1) -coloring - any uniform partition of vertices into this number of colors should have exactly two vertices per color, but two parts of a bipartite graph cannot be divided into pairs, since they contain an odd number of vertices . Therefore, the uniform chromatic threshold of this graph is2n+2 {\ displaystyle 2n + 2}   , which is significantly greater than its uniform chromatic number equal to two.

Hajnal Theorem - Semeredi

Brooks theorem states that any connected graph with maximal degreeΔ {\ displaystyle \ Delta}   It hasΔ {\ displaystyle \ Delta}   -coloring with two exceptions ( full graphs and odd loops). However, this coloring can be generally far from uniform. Pal Erdös [3] hypothesized that uniform coloring is possible with just one additional color - any graph with a maximum degreeΔ {\ displaystyle \ Delta}   has uniform coloring withΔ+one {\ displaystyle \ Delta +1}   flowers. HappeningΔ=2 {\ displaystyle \ Delta = 2}   without any difficulties (any combination of paths and loops can be evenly colored using repeating patterns with three colors with small corrections for closed loops). HappeningΔ+one=n/3 {\ displaystyle \ Delta + 1 = n / 3}   decided Corradi and Hainal [7] . The complete hypothesis was proved by Hainal and Cemeredi [4] and it is now known as the Hainal – Cemeredi theorem. Their initial proof was long and complicated. A simpler proof was given by Kirsted and Kostochka [8] . The polynomial time algorithm for finding uniform colorings with this number of colors was described by Kirsted and Kostochka. They attribute to Marcelo Midlarz and Endre Cemeredi another, previously developed, unpublished polynomial time algorithm. Kirsted and Kostochka also announced a strengthened version of the theorem that a uniform k- coloring exists if the degrees of any two adjacent vertices add up to no more than2k+one {\ displaystyle 2k + 1}   However, the evidence was never published.

Meyer [6] conjectured in the form of a Brooks theorem for uniform coloring - any connected graph with a maximum degreeΔ {\ displaystyle \ Delta}   has uniform coloring withΔ {\ displaystyle \ Delta}   or fewer colors, with the exception of full graphs and odd loops. A reinforced version of the hypothesis states that each such graph has uniform coloring with exactlyΔ {\ displaystyle \ Delta}   with colors, with the exception of an additional exception, a complete bipartite graph in which both shares have the same odd number of vertices [1] .

Seymour [9] proposed a strengthening of the Hajnal – Szemeredi theorem, which also includes the Dirac theorem that dense Hamiltonian graphs — he conjectured that if any vertex in a graph with n vertices has at leastkn/(k+one) {\ displaystyle kn / (k + 1)}   neighbors, then the graph contains as a subgraph a graph formed by connecting vertices that are no more than k steps in the n- cycle. The case k = 1 is the Dirac theorem itself. The Hainal – Semeredi theorem can be covered by this hypothesis by applying the hypothesis for large k values ​​to complement the graph and using continuous sequences of vertices from the n- cycle as color classes. Seymour’s conjecture was proved for graphs in which n is large enough compared to k [10] . The proof uses some profound means, including the Hainal-Szemeredi theorem itself.

Another generalization of the Hajnal – Szemeredi theorem is the Bollobash – Eldridge – Katlin hypothesis (or, for brevity, the BEC hypothesis) [11] . It states that if G 1 and G 2 are graphs with n vertices with maximum degreeΔone {\ displaystyle \ Delta _ {1}}   andΔ2 {\ displaystyle \ Delta _ {2}}   respectively, and if(Δone+one)(Δ2+one)⩽n+one {\ displaystyle (\ Delta _ {1} +1) (\ Delta _ {2} +1) \ leqslant n + 1}   then G 1 and G 2 can be packaged. That is, G 1 and G 2 can be represented on the same set of n vertices without common edges. The Hainal – Szemerédi theorem is a special case of the hypothesis in which G 2 is a union of disjoint cliques . Catlin [12] gives a similar but stronger condition onΔone {\ displaystyle \ Delta _ {1}}   andΔ2 {\ displaystyle \ Delta _ {2}}   in which such packaging is guaranteed to exist.

Special cases of graphs

For any tree with a maximum degreeΔ {\ displaystyle \ Delta}   uniform chromatic number does not exceed

one+⌈Δ/2⌉{\ displaystyle 1+ \ lceil \ Delta / 2 \ rceil}   [6]

with the worst case on the star. However, most trees have a significantly lower uniform chromatic number - if a tree with n vertices hasΔ⩽n/3-O(one) {\ displaystyle \ Delta \ leqslant n / 3-O (1)}   , then it has a uniform coloring with only three colors [13] . Furmanchik [1] studied the uniform chromatic number of graph products .

Computational complexity

We also studied the problem of finding uniform colorings with as few colors as possible (below the Hajnal - Szemeredi border). Direct reduction from graph coloring to uniform coloring can be proved by adding a sufficient number of isolated vertices to the graph, which shows that checking whether the graph has uniform coloring with a given number of colors (more than two) is NP-complete . However, the problem becomes more interesting when it is limited to a special class of graphs or in terms of . Bodlander and Fomin [14] showed that if graph G and the number of colors c are given , we can check whether G allows a uniform c- coloring in time O ( n O ( t ) ), where t is the tree width of graph G. In particular, uniform coloring can be solved optimally in polynomial time for trees (as is known thanks to Chen and Lee [15] ) and outerplanar graphs . The polynomial time algorithm for uniform coloring of split graphs is also known [16] . However, Fellows, Fomin, Lokshtanov et al. [17] proved that when the tree width is a parameter of the algorithm, the problem is W [1] -difficult. Thus, it is unlikely that there is a polynomial time algorithm independent of this parameter, or even that the dependence on the parameter can be put out of the exponent in the work time formula.

Applications

One of the reasons for considering uniform coloring was proposed by Meyer [6] , relating to scheduling problems. In this application, the vertices of the graph represent a set of tasks to perform, and the edges connect two tasks that cannot be performed simultaneously. The coloring of this graph represents a partition of tasks into subsets that can be performed simultaneously. Then the number of colors in the coloring corresponds to the number of steps required to complete the task. According to the agreements on load balancing , it is desirable to perform the same or almost the same number of tasks at each step, and such balancing is exactly what gives uniform coloring. Furmanchik [1] mentioned the specific application of this type of schedule problem, namely, the distribution of university courses by academic hours so that courses are distributed equally across available time slots in order to avoid assigning incompatible pairs of courses at the same time.

The Hajnal – Szemeredi theorem was also used to limit the variance of the sums of random variables with a limited dependence [18] [19] . If (as in the condition ) each variable depends on the maximumΔ {\ displaystyle \ Delta}   others, uniform coloring of the dependency graph can be used to partition variables into independent subsets within which can be calculated, which will give more accurate boundaries for variance than when partitioned in an uneven way.

Notes

  1. ↑ 1 2 3 4 Furmańczyk, 2006 .
  2. ↑ Note that when k is greater than the number of graph vertices, there always exists a uniform coloring with k colors in which all color classes have zero or one vertex in the class, so that any graph has a uniform chromatic threshold.
  3. ↑ 1 2 Erdős, 1964 .
  4. ↑ 1 2 Hajnal, Szemerédi, 1970 .
  5. ↑ Kierstead, Kostochka, Mydlarz, Szemerédi, 2010 , p. 217–224.
  6. ↑ 1 2 3 4 Meyer, 1973 .
  7. ↑ Corrádi, Hajnal, 1963 .
  8. ↑ Kierstead, Kostochka, 2008 .
  9. ↑ Seymour, 1974 .
  10. ↑ Komlós, Sárközy, Szemerédi, 1998 .
  11. ↑ Bollobás, Eldridge, 1978 .
  12. ↑ Catlin, 1974 .
  13. ↑ Bollobás, Guy, 1983 .
  14. ↑ Bodlaender, Fomin, 2005 .
  15. ↑ Chen, Lih, 1994 .
  16. ↑ Chen, Ko, Lih, 1996 .
  17. ↑ Fellows, Fomin, Lokshtanov, 2007 .
  18. ↑ Pemmaraju, 2001 .
  19. ↑ Janson, Ruciński, 2002 .

Literature

  • Henry A. Kierstead, Alexandr V. Kostochka, Marcelo Mydlarz, Endre Szemerédi. A fast algorithm for equitable coloring // Combinatorica. - 2010 .-- T. 30 , no. 2 . - ISSN 0209-9683 . - DOI : 10.1007 / s00493-010-2483-5 .
  • Hans L. Bodlaender, Fedor V. Fomin. Equitable colorings of bounded treewidth graphs // Theoretical Computer Science. - 2005.- T. 349 , no. 1 . - S. 22-30 . - DOI : 10.1016 / j.tcs.2005.09.09.027 .
  • Bollobás B., Eldridge SE Packings of graphs and applications to computational complexity // Journal of Combinatorial Theory . - 1978. - T. 25 , no. 2 . - S. 105–124 . - DOI : 10.1016 / 0097-3165 (78) 90073-0 .
  • Béla Bollobás, Richard K. Guy. Equitable and proportional coloring of trees // Journal of Combinatorial Theory . - 1983 .-- T. 34 , no. 2 . - S. 177–186 . - DOI : 10.1016 / 0095-8956 (83) 90017-5 .
  • Paul A. Catlin. Subgraphs of graphs. I. // Discrete Math .. - 1974. - T. 10 , no. 2 . - S. 225–233 . - DOI : 10.1016 / 0012-365X (74) 90119-8 .
  • Bor-Liang Chen, Ko-Wei Lih. Equitable coloring of trees // Journal of Combinatorial Theory . - 1994 .-- T. 61 , no. 1 . - S. 83–87 . - DOI : 10.1006 / jctb.1994.1032 .
  • Bor-Liang Chen, Ming-Tat Ko, Ko-Wei Lih. Equitable and m -bounded coloring of split graphs // Combinatorics and Computer Science (Brest, 1995). - Berlin: Springer-Verlag, 1996. - T. 1120. - S. 1-5. - (Lecture Notes in Computer Science). - ISBN 978-3-540-61576-7 . - DOI : 10.1007 / 3-540-61576-8_67 .
  • Corrádi K., András Hajnal. On the maximal number of independent circuits in a graph // Acta Mathematica Academiae Scientiarum Hungaricae. - 1963. - T. 14 , no. 3-4 . - S. 423–439 . - DOI : 10.1007 / BF01895727 .
  • Paul Erdős . Problem 9 // Theory of Graphs and its Applications / Fieldler M. .. - Prague: Czech Acad. Sci. Publ., 1964. - S. 159.
  • Michael Fellows, Fedor V. Fomin, Daniel Lokshtanov, Frances Rosamond, Saket Saurabh, Stefan Szeider, Carsten Thomassen. On the complexity of some colorful problems parameterized by treewidth // Combinatorial optimization and applications . - Berlin: Springer-Verlag, 2007.- T. 4616. - S. 366-377. - (Lecture Notes in Computer Science). - ISBN 978-3-540-73555-7 . - DOI : 10.1007 / 978-3-540-73556-4_38 .
  • Hanna Furmańczyk. Equitable coloring of graph products // Opuscula Mathematica . - 2006. - T. 26 , no. 1 . - S. 31–44 .
  • András Hajnal, Endre Szemerédi. Proof of a conjecture of P. Erdős // Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969). - North-Holland, 1970. - S. 601-623.
  • Svante Janson, Andrzej Ruciński. The infamous upper tail // Random Structures & Algorithms. - 2002. - T. 20 , no. 3 . - S. 317–342 . - DOI : 10.1002 / rsa.10031 .
  • A short proof of the Hajnal-Szemerédi theorem on equitable coloring // Combinatorics, Probability and Computing . - 2008. - T. 17 , no. 2 . - S. 265–270 . - DOI : 10.1017 / S0963548307008619 .
  • János Komlós, Gábor N. Sárközy, Endre Szemerédi. Proof of the Seymour conjecture for large graphs // Annals of Combinatorics. - 1998. - T. 2 , no. 1 . - S. 43-60 . - DOI : 10.1007 / BF01626028 .
  • Walter Meyer. Equitable coloring // American Mathematical Monthly . - 1973. - T. 80 , no. 8 . - S. 920–922 . - DOI : 10.2307 / 2319405 .
  • Sriram V. Pemmaraju. Equitable colorings extend Chernoff-Hoeffding bounds // Proc. 12th ACM-SIAM Symp. Discrete Algorithms (SODA 2001) . - 2001. - S. 924–925. - (Soda '01). - ISBN 9780898714906 . .
  • Paul Seymour. Problem section // Combinatorics: Proceedings of the British Combinatorial Conference 1973 / McDonough TP, Mavron VC. - Cambridge, UK: Cambridge Univ. Press, 1974. - S. 201–202. .

Links

  • ECOPT A Branch and Cut algorithm for solving the Equitable Coloring Problem
Source - https://ru.wikipedia.org/w/index.php?title=Uniform_coloring&oldid=99949144


More articles:

  • Musaev, Ayapbergen
  • Concrete Roman
  • Between Two Times
  • Lannilis
  • The Gudovac Massacre
  • German Football Museum
  • Sadykhov, Rauf Khosrovovich
  • City Garden (Sofia)
  • Ceratia
  • Khatlon Buddha

All articles

Clever Geek | 2019