Title:
Automated Conjecture-making and the Independence Number of a Graph
Abstract:
We will discuss a new implementation of Fajtlowicz’s Dalmatian conjecture-making heuristic in an open-source Sage package. Our program can be used to make invariant-relation conjectures for many kinds of mathematical objects.
An \textit{independent set} in a graph is a set of vertices which are pairwise non-adjacent. The independent set decision problem is NP-complete. The \textit{independence number} of a graph is the cardinality of a maximum independent set. We will discuss a few existing bounds for the independence number of a graph, and the use of our program for finding new bounds.