Coloring complexity of graphs
It looks fairly similar to 


  Coloring random graphs online without creating monochromatic subgraphs (Reto Spöhel, Torsten Mütze, and Thomas Rast)
  Proceedings of the 22nd annual ACM-SIAM Symposium on Discrete Algorithms (SODA '11), PR 137, 145-158.



SODA PDF
Journal version
Conference proceedings