The Killer Appears

My students and colleagues know graph E?ow as “the killer” because it is a counterexample to a great many conjectures. After implementing Pepper’s idea of iterating the current lower bounds over the subgraphs induced on the even levels with respect to the vertices, I reported to him that there still wasn’t equality of alpha and this improved lower bound for alpha for all graphs. He asked for an example. Amazingly the killer reared its ugly head! Its the smallest graph that was an example.

Clearly, iterating the lower bounds over the even levels will never work here. What I didn’t include was an initial calculation of the theoretical lower bound before moving on to the even levels. Since residue of the killer equals 4, this graph will be solved.

Now after adding a separate calculation of the lower bounds for the whole graph, and then doing our best on the even levels, the next graph where equality doesn’t hold is F?q`o.


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