On nearly regular co-critical graphs (Q1126306)

A graph \(G\) is \((K_3,K_3)\)-co-critical if the edges of \(G\) can be coloured with two colours without obtaining a monochromatic triangle, but adding any new edge to the graph, this kind of ``good'' colouring is impossible. The question is how small the maximum degree \(\Delta\) of a \((K_3,K_3)\)-co-critical graph can be. It is shown that \(\Delta= O(n^{3/4})\) by a simple constructive example. Still there is a considerable gap between the trivial lower bound \(c\sqrt n\) for \(\Delta\) and this upper bound.