明,如果存在多项式时间染色算法使得对每个图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. USA
6 明，如果存在多项式时间染色算法使得对每个图 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
[67] M. Caramia and P. Dell'Olmo. Bounding vertex coloring by truncated multistage branch and bound, Networks,44(4)(2004,231-242 168 M. Kubale and B. Jackowski. A generalized implicit enumeration algorithm for graph coloring. Communications of the ACM, 28(1985), 412-418 [ 69]A. Mehrotra and M. Trick, A column generation approach for graph coloring. INFORMS Journal On Computing, 8(4)(1996), 344-354 [70]SR. Vegdahl, Using node merging to enhance graph coloring In PLD/ 99: Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation (1999), 150-154, ACM Press, New York, NY, USA [71]F. Herrmann and A. Hertz, Finding the chromatic number by means of critical graphs Journal of Experimental Algorithmics, 7(2002), p10 [ G.A. Kochenberger, F. Glover, B. Alidaee, and C. Rego, An unconstrained quadratic binary approach to the vertex coloring problem. Annals ofoperations Research, 139(1)(2005), 229-241 [73 A. Wigderaon, improving the performance guarantee for approximate graph coloring, Journal of the ACa,30(1983),729-735 174] B. Berger and J. Rompel. a better permance guarantee for approximate graph coloring Algorithmica, 5(1990), 459-466 75]M. M. Halldorsson, A still better performance guarantee for approximate graph coloring, Processing Letters, 45(1993),19-23 [76] M. Bellare, O. Goldreich, and M. Sudan, Free bits, PCPs and non-approximabil ity -towards tight results, SIAMJ. Comp. 27(1998),804-915 [77]A Blum, and D Karger, An O(n)-coloring algorithm for 3-colorable graphs, Information Processing Letters, 61(1997), 49-53 78]L. J. Cowen, W. Goddard, and C. E. Jesurum, Coloring with defect, Proc. &th Ann ACM-SIAM Symp. on Discrete AlgorithmS, ACM-SIAM, (1997), 548-557 [79]R. Duh, and M. Furer, Approximation of k-set cover by semi-local optimization, Proc. 29th Ann. ACM Symp. on Theory of Comp., ACM, (1997), 256-265 80 D. Karger, R. Motwani, and M. Sudan, Approximate graph coloring by semidefinite programming, J. ACM, 45(1998), 246-265. E n Proceedings of the 35AnnuaI IEEE Symposium on Foundations of Computer Science, (1994), 2-13 81] Crivelevich, and B. Sudakov, Appr oximate coloring of uniform hypergraphs, Proc. 6th Ann. European Symp. on Algorithms, Lecture Notes in Comput. Sci., Springer-Verlag, (1998), 477-489 [82] T. Hofmeister, and H. Lefmann, Approximating maximum independent sets in uniform hypergraphs, Proc. 23rd International Symp. on Mathematical Foundations of Comput. Sci Lecture Notes in Comput. Sci. 1450, Springer-Verlag, (1998), 562-570 [83]U. Feige, and J. Kilian, Zero knowledge and the chromatic number, Journal of Computer and System Sciences, 57(2)(1998),187-199 84]V. Kumar, Approximating circular arc colouring and bandwidth allocation in all-optical ring networks, Proc. Ist Int. Workshop on Approximation Algorithms for Combinatorial Problems ecture Notes in Comput. Sci., Springer-Verlag, (1998), 147-158
7 [67] M. Caramia and P. Dell'Olmo. Bounding vertex coloring by truncated multistage branch and bound, Networks, 44(4) (2004), 231-242. [68] M. Kubale and B. Jackowski. A generalized implicit enumeration algorithm for graph coloring. Communications of the ACM, 28 (1985), 412-418. [69] A. Mehrotra and M. Trick, A column generation approach for graph coloring. INFORMS Journal On Computing, 8(4) (1996), 344-354. [70] S.R. Vegdahl, Using node merging to enhance graph coloring. In PLDI '99: Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, (1999), 150-154, ACM Press, New York, NY, USA. [71] F. Herrmann and A. Hertz, Finding the chromatic number by means of critical graphs. Journal of Experimental Algorithmics, 7(2002), p10. [72] G.A. Kochenberger, F. Glover, B. Alidaee, and C. Rego, An unconstrained quadratic binary approach to the vertex coloring problem. Annals of Operations Research, 139(1) (2005), 229-241. [73] A. Wigderaon, improving the performance guarantee for approximate graph coloring, Journal of the ACM, 30(1983), 729-735. [74] B. Berger and J. Rompel. A better permance guarantee for approximate graph coloring. Algorithmica, 5(1990), 459-466. [75] M. M. Halldórsson, A still better performance guarantee for approximate graph coloring, Information Processing Letters，45(1993), 19-23. [76] M. Bellare, O. Goldreich, and M. Sudan, Free bits, PCPs and non-approximability - towards tight results, SIAM J. Comp. 27(1998), 804-915. [77] A. Blum, and D. Karger, An 3 14 O n( ) -coloring algorithm for 3-colorable graphs, Information Processing Letters，61(1997), 49-53. [78] L. J. Cowen, W. Goddard, and C. E. Jesurum, Coloring with defect, Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, (1997), 548-557. [79] R. Duh, and M. Fürer, Approximation of k-set cover by semi-local optimization, Proc. 29th Ann. ACM Symp. on Theory of Comp., ACM, (1997), 256-265. [80] D. Karger, R. Motwani, and M. Sudan, Approximate graph coloring by semidefinite programming, J. ACM，45(1998), 246-265. 或见 Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, (1994), 2-13. [81] M. Krivelevich, and B. Sudakov, Approximate coloring of uniform hypergraphs, Proc. 6th Ann. European Symp. on Algorithms, Lecture Notes in Comput. Sci., Springer-Verlag, (1998), 477-489. [82] T. Hofmeister, and H. Lefmann, Approximating maximum independent sets in uniform hypergraphs, Proc. 23rd International Symp. on Mathematical Foundations of Comput. Sci., Lecture Notes in Comput. Sci. 1450, Springer-Verlag, (1998), 562-570. [83] U. Feige, and J. Kilian, Zero knowledge and the chromatic number, Journal of Computer and System Sciences, 57(2)(1998), 187-199. [84] V. Kumar, Approximating circular arc colouring and bandwidth allocation in all-optical ring networks, Proc. 1st Int. Workshop on Approximation Algorithms for Combinatorial Problems, Lecture Notes in Comput. Sci., Springer-Verlag, (1998), 147-158