Sunday, July 16, 2006

Trying very hard to prove that a graph with chi > 1/2 ( omega + Delta + 2 ) has 2-connected complement. Able to show this for graphs with chi > 1/2 ( omega + Delta + 3 ); only 1/2 off. Have severely restricted possible counterexamples -- after removing a vertex disconnecting the complement, there are two components which must have the same minimal degree, the graph has independence number at most 4, the complements of each of the two components in the complement have the property that the induced subgraph on all vertices of maximal degree has triangle free complement. etc.

1 comment:

Anonymous said...

you're a magic square.