Greedy coloring in graph theory is a coloring of the vertices of an undirected graph created by a greedy algorithm that goes through the vertices of the graph in some predetermined sequence and assigns each vertex the first available color. Greedy algorithms, in the general case, do not produce the smallest possible number of colors, however they are used in mathematics as a technique for proving other results related to coloring, as well as in computer programs for coloring with a small number of colors.
Content
- 1 Greedy algorithms are not always good
- 2 Optimal ordering
- 3 Heuristic sequencing strategies
- 4 Alternative color schemes
- 5 notes
- 6 Literature
Greedy algorithms are not always good.
A corona (a complete bipartite graph K n , n with perfect matching edges removed) is a particularly bad case for a greedy algorithm - if two vertices belonging to a remote edge from a matching are placed in a sequence of vertices, the greedy algorithm uses n colors, while the optimal the number for such a graph is two colors. There are also graphs for which, with a high probability, a randomly selected sequence of vertices will lead to the use of the number of colors significantly larger than the minimum required [1] . Thus, it is very important to carefully choose the sequence in which the vertices are traversed by the greedy algorithm.
For a given graph G and a number k , determining whether there is an order of vertices of a graph G that leads to the use of k and more colors by the greedy algorithm is an NP-complete problem. This, in particular, means that it is difficult to find the worst case for the graph G [2] .
Optimal Ordering
The vertices of any graph can always be ordered in such a way that the greedy algorithm gives an optimal coloring. So, for any optimal coloring, we renumber first (in decreasing order) the vertices from the smallest-sized set of identically colored vertices. Then we renumber the second largest set, and so on. If we now apply the greedy algorithm with this order of vertices, the resulting coloring will be optimal. More strictly, for graphs with (this family includes chordal graphs , compatibility graphs , and distance-inheritable graphs ) there is an order that is optimal for both the graph itself and all its generated subgraphs [3] . However, finding this optimal order for an arbitrary graph is an NP-complete problem (if only because its solution can be used to obtain the optimal coloring of the graph, that is, the solution of an NP-complete problem), and determining whether a perfect ordering of vertices exists in the graph also is an NP-complete problem [4] . For this reason, heuristic algorithms are used to color the graph in order to reduce the number of colors, although they do not provide the optimal number of colors.
Heuristic sequencing strategies
Typically, to order the vertices for the greedy algorithm, select the vertex v with a minimal degree , arrange the remaining vertices, and put v at the end of the list. If any subgraph of G contains vertices with a degree not exceeding d , then the greedy coloring algorithm for this order of vertices uses a maximum of d + 1 colors [5] . The smallest of d is usually called the graph.
For a graph with a maximum degree of Δ, any greedy algorithm uses a maximum of Δ + 1 colors. Brooks' theorem states that with the exception of two exceptions ( clicks and odd cycles ), no more than Δ colors are needed for coloring. One of the proofs of the Brooks theorem uses vertex ordering, in which the first two vertices are adjacent to the final vertex, but not adjacent to each other. Such a sequence has for each vertex at least one previous vertex belonging to a neighborhood. For a sequence of vertices with such properties, the greedy algorithm uses a maximum of Δ colors [6] .
Alternative color schemes
You can build a greedy algorithm in which the vertices of a given graph are painted in a predetermined sequence, but in which the color is not necessarily selected the first one that comes from free colors. As an alternative strategy for color selection, approaches to have been studied. In the problem of online coloring of a graph, the vertices of the graph are presented with a coloring algorithm sequentially one at a time in an arbitrary order. The algorithm should choose the color of each vertex, relying only on the colors and adjacency of the already processed vertices. In this context, the quality of the color selection strategy is measured by the , the ratio of the number of colors used to the optimal number of colors for coloring the graph.
If no other constraints are specified on the graph, the optimal competitive ratio is only slightly sublinear [7] . However, for interval graphs , a constant is possible as a competitive relation [8] , while for bipartite and sparse graphs, a logarithmic relation can be obtained [9] . Moreover, for sparse graphs, the usual strategy of choosing the first available color gives this estimate and it can be shown that this estimate is lower for the competitive relationship of any online coloring algorithm [9] .
Notes
- ↑ Kučera, 1991 .
- ↑ Zaker, 2006 .
- ↑ Chvátal, 1984 .
- ↑ Middendorf, Pfeiffer, 1990 .
- ↑ Welsh, Powell, 1967 ; Johnson, 1979 ; Sysło, 1989 ; Maffray, 2003
- ↑ Lovász, 1975 .
- ↑ Lovász, Saks, Trotter, 1989 ; Vishwanathan, 1990
- ↑ Kierstead, Trotter, 1981 .
- ↑ 1 2 Irani, 1994 .
Literature
- Václav Chvátal. Topics in Perfect Graphs / Claude Berge, Václav Chvátal. - Amsterdam: North-Holland, 1984. - T. 21. - S. 63-68. - (Annals of Discrete Mathematics). As cited in Maffray, 2003 .
- Sandy Irani. Coloring inductive graphs on-line // Algorithmica. - 1994. - T. 11 , no. 1 . - S. 53–72 . - DOI : 10.1007 / BF01294263 .
- HA Kierstead, WA Trotter. An extremal problem in recursive combinatorics // Congress. Numer .. - 1981. - T. 33 . - S. 143-153 . As quoted in Irani, 1994 .
- Luděk Kučera. The greedy coloring is a bad probabilistic algorithm // Journal of Algorithms. - 1991. - T. 12 , no. 4 . - S. 674-684 . - DOI : 10.1016 / 0196-6774 (91) 90040-6 .
- DS Johnson. Proc. 5th Southeastern Conf. Combinatorics, Graph Theory and Computation. - Winnipeg: Utilitas Mathematica, 1979. - S. 513-527 . As cited in Maffray, 2003 .
- L. Lovász. Three short proofs in graph theory // Journal of Combinatorial Theory, Series B. - 1975.- Vol. 19 , no. 3 . - S. 269—271 . - DOI : 10.1016 / 0095-8956 (75) 90089-1 .
- L. Lovász, ME Saks, WA Trotter. An on-line graph coloring algorithm with sublinear performance ratio // Discrete Mathematics. - 1989.- T. 75 , no. 1-3 . - S. 319-325 . - DOI : 10.1016 / 0012-365X (89) 90096-4 .
- Frédéric Maffray. Recent Advances in Algorithms and Combinatorics / Bruce A. Reed, Sales Cláudia L. - Springer-Verlag, 2003. - T. 11. - P. 65–84. - (CMS Books in Mathematics). - ISBN 0-387-95434-1 . - DOI : 10.1007 / 0-387-22444-0_3 .
- Matthias Middendorf, Frank Pfeiffer. On the complexity of recognizing perfectly orderable graphs // Discrete Mathematics. - 1990. - T. 80 , no. 3 . - S. 327—333 . - DOI : 10.1016 / 0012-365X (90) 90251-C .
- Maciej M. Sysło. Sequential coloring versus Welsh-Powell bound // Discrete Mathematics. - 1989.- T. 74 , no. 1-2 . - S. 241-243 . - DOI : 10.1016 / 0012-365X (89) 90212-4 .
- S. Vishwanathan. Proc. 31st IEEE Symp. Foundations of Computer Science (FOCS '90). - 1990. - T. 2 . - S. 464-469 . - ISBN 0-8186-2082-X . - DOI : 10.1109 / FSCS.1990.89567 .
- DJA Welsh, MB Powell. An upper bound for the chromatic number of a graph and its application to timetabling problems // The Computer Journal. - 1967. - T. 10 , no. 1 . - S. 85-86 . - DOI : 10.1093 / comjnl / 10.1.85 .
- Manouchehr Zaker. Results on the Grundy chromatic number of graphs // Discrete Mathematics. - 2006. - T. 306 , no. 2-3 . - S. 3166-3173 . - DOI : 10.1016 / j.disc.2005.06.06.044 .