Vertex (n, k)-choosability of graphs

Abstract

Let G = (V, E), connected, simple graph of order n and size m and let V(G) = {1, 2, ..., n}.  A graph G = (V, E) is said to be vertex (n, k)-choosable, if there exists a collection of subsets of the vertex set, {S_k(v) : v ∈ V} of cardinality k, such that S_k(u) ∩ S_k(v) = ∅ for all uv ∈ E(G).  This paper initiates a study on vertex (n, k)-choosable graphs and finds the different integer values of k, for which the given graph is vertex (n, k)-choosable.