An Algorithm for the Chromatic Number of a Graph

ABSTRACT

Christofides' algorithm for finding the chromatic number of a graph is improved both in speed and memory space by using a depth-first search rule to search for a shortest path in a reduced subgraph tree.

REFERENCES

• 1: CHRISTOFIDES, N. An algorithm for the chromatic number of a graph. Computer J. 14, 1 (Feb. 1971), 38-39.
• 2: HARAR~, F. Graph Theory. Addison-Wesley, Reading, Mass., 1969.
• 3: ERI)Ss, P., AND P~}~NYI, A. On random graphs. I. Publicationes Mathematicae (Debrecen) 6 (1959), 290-297.
• 4: EaD{3S, P., AND RgNYI, A. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 5A (1960), 17-61.
• 5: ERDOS, P., AND RgNYX, A. On the strength of connectedness of a random graph. Acta Math. Acad. Sci. Hung. 12 (1961), 261-267.
• 6: ERD~3S, P., AND R}~NYI, A. Oil the existence of a factor of degree one of a connected random graph. Acta Math. Acad. Sci. Hung. 17 (1966), 359-368.
• 7: MATULA, D. On the complete subgraphs of a random graph, Proc. of the Second Chapel Hill Conference on Combinatorial Mathematics and Its Application, U. of North Carolina, 1970, pp. 356-369.
• 8: WIncH, N. The Programming Language Pascal. Berichte der Fachgruppe Computer-Wissenschaften, Eidgenossische Technische Hochschule, Zurich, Switzerland, 1970.
• 9: Gordon D. Mulligan , D. G. Corneil, Corrections to Bierstone's Algorithm for Generating Cliques, Journal of the ACM (JACM), v.19 n.2, p.244-247, April 1972 [doi>10.1145/321694.321698]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Measurement, Performance, Theory, Verification