New models of graph-bin packing

In Bujtás et al. (2011) [4] the authors introduced a very general problem called Graph-Bin Packing (GBP). It requires a mapping μ:V(G)→V(H)μ:V(G)→V(H) from the vertex set of an input graph G into a fixed host graph H  , which, among other conditions, satisfies that for each pair u,vu,v of adjacent vertices the distance of μ(u)μ(u) and μ(v)μ(v) in H is between two prescribed bounds. In this paper we propose two online versions of the Graph-Bin Packing problem. In both cases the vertices can arrive in an arbitrary order where each new vertex is adjacent to some of the previous ones. One version is a Maker–Breaker game whose rules are defined by the packing conditions. A subclass of Maker-win input graphs is what we call ‘well-packable’; it means that a packing of G   is obtained whenever the mapping μ(u)μ(u) is generated by selecting an arbitrary feasible vertex of the host graph for the next vertex of G in each step. The other model is connected-online packing where we are looking for an online algorithm which can always find a feasible packing. In both models we present some sufficient and some necessary conditions for packability. In the connected-online version we also give bounds on the size of used part of the host graph.