明,如果存在多项式时间染色算法使得对每个图G都可使用不多于2(G)种色进行正常顶 点染色,则必定存在G的z(G)顶点染色有效算法1m1。这表明,对图的点染色问题,找 近似比等于常数的多项式时间近似算法与找(G)顶点染色的(有效)精确算法一样困难。 下面介绍点染色问题的几种非多项式时间算法和简单的近似算法。更多的算法可参见文 献[52}[115],其中[52}-{58]是与图的点染色算法有关的专著,[59}-[72]研究图的点染色问 题的各种精确算法,[73}-[89研究图的点染色问题的近似算法及其性能,在不同条件下给出 了较低近似比的染色算法,[9o-[1l将邻域方法、禁忌搜索和局部搜索方法、模拟退火法 人工神经网络、遗传算法、蚁群算法等方法以及其它一些启发式方法用于图的点染色问题。 [12[15讨论点染色的相关计算复杂性问题。 52 G Chartrand, O. R Oellermann, Applied and Algorithmic Graph Theory, McGraw-Hill, Inc New York,(1993),283-310 53 M.R. Garey and D.s. Johnson, Computers and Intractibility: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979 54] D.S. Hochbaum, Approximation Algorithms for NP-hard ProblemS, International Thomson Publishing Inc,1997(影印本:NP难解问题的近似算法,世界图书出版公司) 55]N. Christofides, Graph Theory: An Algorithmic Approach, Academic Press, New York, (1990),58-78 56]S Even, Algorithmic Combinatorics, Macmillan, New York, 1973 57]R. Gould, Graph Theory, Benjamin Cummings, Menlo, Park, CA(1988 58]D W. Matula, G. Marble, and J D. Isaacson, Graph colouring algorithms, in Graph Theory and Computing(Read Ed.), Academic Press, New York, (1972)109-122 59]D. Brelaz, New methods to color the vertices of a graph, Communications of the Association y,22(1979)251-256 [60 E.C.Sewell. An Improved algorithm for exact graph coloring, in"Cliques, Coloring and Satisfiability"(DIMACS Series in Discrete Mathematics and Theoretical Computer Science), 26(1996), 359-373. American Mathematical Society, Providence, RI, USA 161 D. Eppstein, Small maximal independent sets and faster exact graph coloring, Journal of Graph Algorithms and ApplicationS, 7(2)(2003), 131-140 [62]N. Christofides, An algorithm for the chromatic number of a graph, The Computer Journal, 4(1971),38-39 163 D G Corneil and B. Graham, An algorithm for determining the chromatic number of a graph, SIAM Journal on Computing, 2(1973), 211-218 64]D. Kirovski and M. Potkonjak, Efficient coloring of a large spectrum of graphs. In DAC 98 Proceedings of the 35th annual conference on Design automation, (1998), 427-432, ACM Press, New York. NY USA [65] Ojvind Johansson, Simple distributed A+l-coloring of graphs, Information Processing Letters,70(1999),229-232 [66]I M. Diaz and P. Zabala, A branch-and-cut algorithm for graph coloring, (2002), 55-62, Ithaca, New York. USA6 明，如果存在多项式时间染色算法使得对每个图 G 都可使用不多于 2 (G) χ 种色进行正常顶 点染色，则必定存在 G 的 χ(G) 顶点染色有效算法[117][118]。这表明，对图的点染色问题，找 近似比等于常数的多项式时间近似算法与找 χ(G) 顶点染色的（有效）精确算法一样困难。 下面介绍点染色问题的几种非多项式时间算法和简单的近似算法。更多的算法可参见文 献[52]~[115]，其中[52]~[58]是与图的点染色算法有关的专著，[59]~[72]研究图的点染色问 题的各种精确算法，[73]~[89]研究图的点染色问题的近似算法及其性能，在不同条件下给出 了较低近似比的染色算法，[90]~[111]将邻域方法、禁忌搜索和局部搜索方法、模拟退火法、 人工神经网络、遗传算法、蚁群算法等方法以及其它一些启发式方法用于图的点染色问题。 [112]-[115]讨论点染色的相关计算复杂性问题。 [52] G. Chartrand, O. R. Oellermann, Applied and Algorithmic Graph Theory, McGraw-Hill, Inc., New York, (1993), 283-310. [53] M.R. Garey and D.S. Johnson, Computers and Intractibility: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979. [54] D.S. Hochbaum, Approximation Algorithms for NP-hard Problems, International Thomson Publishing Inc., 1997 (影印本：NP 难解问题的近似算法，世界图书出版公司)。 [55] N. Christofides, Graph Theory: An Algorithmic Approach, Academic Press, New York, (1990), 58-78. [56] S. Even, Algorithmic Combinatorics, Macmillan, New York, 1973. [57] R. Gould, Graph Theory, Benjamin Cummings, Menlo, Park, CA(1988). [58] D.W. Matula, G. Marble, and J.D. Isaacson, Graph colouring algorithms, in Graph Theory and Computing (Read Ed.), Academic Press, New York, (1972) 109-122. [59] D. Brelaz, New methods to color the vertices of a graph, Communications of the Association for Computing Machinery, 22(1979), 251-256. [60] E.C.Sewell. An Improved algorithm for exact graph coloring, in “Cliques, Coloring and Satisfiability”. (DIMACS Series in Discrete Mathematics and Theoretical Computer Science), 26 (1996), 359-373. American Mathematical Society, Providence, RI, USA. [61] D. Eppstein, Small maximal independent sets and faster exact graph coloring, Journal of Graph Algorithms and Applications, 7(2) (2003), 131-140. [62] N. Christofides, An algorithm for the chromatic number of a graph, The Computer Journal, 14(1971), 38-39. [63] D. G. Corneil and B. Graham, An algorithm for determining the chromatic number of a graph, SIAM Journal on Computing, 2(1973), 211-218. [64] D. Kirovski and M. Potkonjak, Efficient coloring of a large spectrum of graphs. In DAC '98: Proceedings of the 35th annual conference on Design automation, (1998), 427-432, ACM Press, New York, NY, USA. [65] Ojvind Johansson, Simple distributed Δ +1-coloring of graphs, Information Processing Letters, 70(1999), 229-232. [66] I.M. Diaz and P. Zabala, A branch-and-cut algorithm for graph coloring, (2002), 55-62, Ithaca, New York, USA