EXTENDED CORE AND CHOOSABILITY OF A GRAPH

YVES AUBRY, JEAN-CHRISTOPHE GODIN AND OLIVIER TOGNIAbstract. A graph G is (a,b)-choosable if for any color list of size aassociated with each vertices, one can choose a subset of b colors suchthat adjacent vertices are colored with disjoint color sets. This papershows an equivalence between the (a,b)-choosability of a graph and the(a,b)-choosability of one of its subgraphs called the extended core. Asan application, this result allows to prove the (5,2)-choosability and(7,3)-colorability of triangle-free induced subgraphs of the triangularlattice.