DeLaVina’s Grafitti.pc

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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s