Seminar on Applied Mathematics
Pierre Hansen, Gerad, Ecole des Hautes Etudes Commerciales, Montreal and Hong Kong Polytechnic
COMPUTERS IN GRAPH THEORY
Abstract: Computers are extensively used in graph applications. They can also help in graph theory, i.e., to provide, suggest or help to obtain conjectures, refutations and proofs. We survey the fairly numerous but dispersed efforts made in this area during the last 25 years. Approaches include specific case enumeration (as in proofs of the four color theorem), graph generation (i.e. when finding new Ramsey numbers), general theorem proving approaches (as in the systems "Graph" and "Graph Theorist"), formula manipulation (as in the system "Ingrid"), interactive conjecture finding (as in "Graph" and several more recent systems), finding conjectures with a priori simple forms and eliminating false or uninteresting ones (as in the system "Graffiti") and applying a metaheuristic to find families of extremal graphs from which conjectures can be deduced (as in the system "AutoGraphiX").