Efficient Graph Packing via Game Colouring
Hal A. Kierstead, Alexandr V. Kostochka · Combinatorics Probability Computing · 2009
The game colouring number gcol(G) of a graphGis the leastksuch that, if two players take turns choosing the vertices of a graph, then either of them can ensure that every vertex has fewer thankneighbours chosen before it, regardless of what choices the other player makes. Clearly gcol(G) ≤ Δ(G)+1. Sauer and Spencer [20] proved that if two graphsG1andG2onnvertices satisfy 2Δ(G1)Δ(G2) <nthen they pack,i.e., there is an embedding ofG1into the complement ofG2. We improve this by showing that if (gcol(G1)−1)Δ(G2)+(gcol(G2)−1)Δ(G1)