Maximum-weight stable sets and safe lower bounds for graph coloring

Andrade, D.V., Resende, M.G.C., Werneck, R.F.: Fast local search for the maximum independent set problem. In: Proceedings of workshop on experimental algorithms, pp. 220–234 (2008)

Applegate D.L., Cook W., Dash S., Espinoza D.G.: Exact solutions to linear programming problems. Oper. Res. Lett. 35(6), 693–699 (2007)

Babel L.: A fast algorithm for the maximum weight clique problem. Computing 52, 31–38 (1994)

Balas E., Xue J.: Minimum weighted coloring of triangulated graphs with application to maximum weight vertex packing and clique finding in arbitrary graphs. SIAM J. Comput. 20(2), 209–221 (1991)

Balas E., Yu C.: Finding a maximum clique in an arbitrary graph. SIAM J. Comput. 15(4), 1054–1068 (1986)

Balas, E., Niehaus, W.: A max-flow based procedure for finding heavy cliques in vertex-weighted graphs. Tech. Rep. MSRR No. 612, GSIA, Carnegie-Mellon University (1995)

Brélaz D.: New methods to color the vertices of a graph. Commun. ACM 22(4), 251–256 (1979)

Busygin S.: A new trust region technique for the maximum weight clique problem. Discret. Appl. Math. 154, 2080–2096 (2006)

Leighton F.T.: A graph coloring problem for large scheduling problems. J. Res. Natl. Bureau Stand. 84, 489–505 (1979)

Gualandi S., Malucelli F.: Exact solution of graph coloring problems via constraint programming and column generation. INFORMS J. Comput. 24(1), 81–100 (2012)

Hansen P., Labbé M., Schindl D.: Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results. Discret. Optim. 6(2), 135–147 (2009)

Held S., Sewell, E.C., Cook, W.: Exact colors project webpage (2010). http://code.google.com/p/exactcolors/

Lund C., Yannakakis M.: On the hardness of approximating minimization problems. J. ACM 41(5), 960–981 (1994)

Malaguti E., Monaci M., Toth P.: An exact approach for the vertex coloring problem. Discret. Optim. 8(2), 174–190 (2011)

Malaguti E., Toth P.: A survey on vertex coloring problems. Int. Trans. Oper. Res. 17, 1–34 (2010)

Mehrotra A., Trick M.A.: A column generation approach for graph coloring. INFORMS J. Comput. 8(4), 344–354 (1996)

Mittelmann H.: Benchmarks for optimization software (2011). http://plato.asu.edu/bench.html

Mycielski J.: Sur le coloriage des graphes. Colloq. Math. 3, 161–162 (1955)

Méndez-Díaz I., Zabala P.: A branch-and-cut algorithm for graph coloring. Discret. Appl. Math. 154(5), 826–847 (2006)

Méndez-Díaz I., Zabala P.: A cutting plane algorithm for graph coloring. Discret. Appl. Math. 156(2), 159–179 (2008)

Porumbel D.C., Hao J.K., Kuntz P.: An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring. Comput. Oper. Res. 37(10), 1822–1832 (2010)

Sewell E.C.: A branch and bound algorithm for the stability number of a sparse graph. INFORMS J. Comput. 10(4), 438–447 (1998)

Steffy, D.E.: Topics in exact precision mathematical programming. Ph.D. thesis, Georgia Institute of Technology (2011)

Titiloye O., Crispin, A.: Graph coloring with a distributed hybrid quantum annealing algorithm. In: Proceedings of the 5th KES international conference on agent and multi-agent systems: technologies and applications, KES-AMSTA’11, Springer, Berlin, pp. 553–562 (2011)

Titiloye O., Crispin A.: Quantum annealing of the graph coloring problem. Discret. Optim. 8(2), 376–384 (2011)

Trick M.: DIMACS graph coloring instances (2002). http://mat.gsia.cmu.edu/COLOR02/

Warren, J., Hicks, I.: Combinatorial branch-and-bound for the maximum weight independent set problem. Technical report, Texas A&M University (2006)

Wu Q., Hao J.K.: Coloring large graphs based on independent set extraction. Comput. Oper. Res. 39(2), 283–290 (2012)

Zuckerman D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3(1), 103–128 (2007)

P.R.J.: A new algorithm for the maximum-weight clique problem. Electron. Notes Discret. Math. 3, 153–156 (1999)

Östergård, P.R.J., Niskanen, S.: Cliquer home page (2010). http://users.tkk.fi/pat/cliquer.html