The graph coloring problem of a graph G=(V,E) can be formulated as a set covering problem, where the ground set is V and the available sets are the maximal (inclusionwise) stable sets of G. Alternatively, it can be expressed as a set packing problem on the same ground set, where the available sets are all stable sets of G. Since the number of variables grows exponentially with the size of G, both linear relaxations require column generation for their optimization. Nevertheless, they give a tight lower bound (called the fractional chromatic number) on the chromatic number of G, hence effective branch and cut (and price) algorithms can be obtained from it. Both formulations are compared and polyhedral results as well as preprocessing procedures, expressed in simple graphical terms, are presented.

Computer-assisted and automated conjecture-making in graph theory is reviewed, focusing on the three operational systems GRAPH, Graffiti and AutoGraphiX (AGX). A series of possible enhancements, mostly through hybridisation of these systems, are proposed as well as several research paths for development of the area.

Conjectures in graph theory have multiple forms and involve graph invariants, graph classes, subgraphs, minors and other concepts in premises and/or conclusions. Various abstract criteria have been proposed in order to find interesting ones with computer-aided or automated systems for conjecture-making. Beginning with the observation that famous theorems (and others) have first been conjectures, if only in the minds of those who obtained them, we review forms that they take. We also give examples of conjectures of such forms obtained with the help of, or by, computers when it is the case. It appears that many forms are unexplored and so computer-assisted and automated conjecture-making in graph theory, despite many successes, is pretty much at its beginning.

Computers are extensively used in graph theory to find values of invariants, such as chromatic number, independence number, diameter, radius and the like, to enumerate graphs of various families and to assist in proofs, also by enumeration. They can also be used to enhance graph theory per se by (i) finding extremal graphs for some invariants or formula involving several invariants, (ii) finding such extremal graphs subject to constraints, (iii) refuting conjectures and/or strengthening them, (iv) finding original conjectures and (v) suggesting proof strategies. The AutoGraphiX 1 and AutoGraphiX 2 systems use global optimization for the purposes listed above: extremal or near-extremal graphs are first obtained with the Variable Neighborhood Search metaheuristic; then three methods, numerical, algebraic and geometric, are applied to find conjectures automatically. This has led to over 60 conjectures and a dozen research papers. The AutoGraphiX 2 system will be described, with a focus on the global optimization routines which are at its heart.