New methods to color the vertices of a graph

ABSTRACT

This paper describes efficient new heuristic methods to color the vertices of a graph which rely upon the comparison of the degrees and structure of a graph. A method is developed which is exact for bipartite graphs and is an important part of heuristic procedures to find maximal cliques in general graphs. Finally an exact method is given which performs better than the Randall-Brown algorithm and is able to color larger graphs, and the new heuristic methods, the classical methods, and the exact method are compared.

REFERENCES

• 1: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• 2: Brelaz, D., de Werra, D., and Nicolier, Y. Compactness and balancing in scheduling. Zeitschrifi fdr Operations Research, Band 21, Heft l, Serie A, 1977, pp. 65-73.
• 3: Dunstan, F. Greedy algorithms for optimization problems. Presented at Euro I meeting, Brussels, Jan. 1975.
• 4: Karp, R.M. Reducibility among combinatorial problems. In Complexity of Computer Computations, R.E. Miller and J.W. Thatcher, Eds., Plenum Press, New York and London, 1972, pp. 85- 103.
• 5: Matula, D., Marble, G., and Isaacson, J. Graph coloring algorithms. In Graph Theory and Computing, Academic Press, New York, 1972, pp. 109-122.
• 6: Randall-Brown, J. Chromatic scheduling and the chromatic number problems. Management Science 19, 4 (Dec. 1972), Part l, 456-463.
• 7: Tehrani, A. Un algorithme de coloration. Cabiers du centre d'etudes de Recherche Operationnelle, Vol. 17, 2-3-4, 1975, pp. 395- 398.
• 8: Welsh, D.J.A., and Powell, M.B. An upper bound for the chromatic number of a graph and its applications to timetabling problems. The Comptr. J. 10 (1967), 85-86.

INDEX TERMS

Keywords:
NP-complete, balancing, comparison of the methods, graph coloring, graph structure, scheduling