List backbone colouring of graphs

Suppose that GG is a graph and that HH is a subgraph of GG. Let LL be a mapping that assigns to each vertex vv of GG a set L(v)L(v) of positive integers. We say that (G,H)(G,H) is backboneLL-colourable if there is a proper vertex colouring cc of GG such that c(v)∈L(v)c(v)∈L(v) for all v∈Vv∈V, and |c(u)−c(v)|⩾2|c(u)−c(v)|⩾2 for every edge uvuv in HH. We say that (G,H)(G,H) is backbone kk-choosable if (G,H)(G,H) is backbone LL-colourable for any list assignment LL with |L(v)|=k|L(v)|=k for all v∈V(G)v∈V(G). The backbone choice number of (G,H)(G,H), denoted by chBB(G,H), is the minimum kk such that (G,H)(G,H) is backbone kk-choosable. The concept of a backbone choice number is a generalization of both the choice number and the L(2,1)L(2,1)-choice number. Precisely, if E(H)=0̸E(H)=0̸, then chBB(G,H)=ch(G), where ch(G) is the choice number of GG; if G=H2G=H2, then chBB(G,H) is the same as the L(2,1)L(2,1)-choice number of HH. In this article, we first show that, if |L(v)|=dG(v)+2dH(v)|L(v)|=dG(v)+2dH(v), then (G,H)(G,H) is LL-colourable, unless E(H)=0̸E(H)=0̸ and each block of GG is a complete graph or an odd cycle. This generalizes a result of Erdős, Rubin, and Taylor on degree-choosable graphs. Second, we prove that chBB(G,H)⩽max{⌊mad(G)⌋+1,⌊mad(G)+2mad(H)⌋}, where mad(G) is the maximum average degree of a graph GG. Finally, we establish various upper bounds on chBB(G,H) in terms of ch(G). In particular, we prove that, for a kk-choosable graph GG, chBB(G,H)⩽3k if every component of HH is unicyclic; chBB(G,H)⩽2k if HH is a matching; and chBB(G,H)⩽2k+1 if HH is a disjoint union of paths with length at most 2.