Efficient Graph Packing via Game Colouring

The game colouring number gcol(G) of a graph G is the least k such that, if two players take turns choosing the vertices of a graph, then either of them can ensure that every vertex has fewer than k neighbours chosen before it, regardless of what choices the other player makes. Clearly gcol(G) <= Delta(G) + 1. Sauer and Spencer [20] proved that if two graphs G(1) and G(2) on n vertices satisfy 2 Delta(G(1))Delta(G(2)) < n then they pack, i.e., there is an embedding of G(1) into the complement of G(2). We improve this by showing that if (gcol(G(1)) - 1)Delta(G(2)) + (gcol(G(2)) - 1)Delta(G(1)) < n then G(1) and G(2) pack. To our knowledge this is the first application of colouring games to a non-game problem.