Efficient Graph Packing via Game Colouring

Source abstract

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 ) ≤ Δ( G )+1. Sauer and Spencer [20] proved that if two graphs G 1 and G 2 on n vertices satisfy 2Δ( G 1 )Δ( 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)Δ( G 2 )+(gcol( G 2 )−1)Δ( 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.