Working on using the following theorem to prove the full Borodin-Kostochka conjecture.

Theorem: If G contains a doubly critical edge and satisfies chi >= Delta >= 6, then G contains a K_Delta.

So, the Borodin-Kostochka conjecture (and more) holds for graphs containing a doubly critical edge. This allows one to try to find a doubly critical edge instead of trying to find a big clique. This works to give a new proof of Brooks' theorem, but it gets intricate for the Borodin-Kostochka condition; however, there is a lot of room to play and it looks very promising (this all uses a decomposition theorem of Lovasz -- actually a modification of it by Catlin).

nqsiq

dxbpgril