After we get a difficult graph, one way to tackle it is to find new bounds that lead to an exact prediction of its independence number. Fajtlowicz’s Grafitti program is one program that makes conjectures about graph theoretic invariants, and can automatedly conjecture bounds.

Ermelinda DeLaVina‘s Grafitti.pc (G.pc) program is another. She was a student of Fajtlowicz, co-developed the Dalmatian version of that program, and then wrote her own program. It uses some of the same conjecturing heuristics, but has additional features. For instance it can conjecture relations between properties; G.pc conjectured a very nice characterization of KE graphs.

Here is a list of G.pc’s conjectures, including some on independence number.

Advertisements