Download PDFOpen PDF in browserMinimum NonChromaticλChoosable GraphsEasyChair Preprint no. 103117 pages•Date: May 31, 2023AbstractFor a multiset \lambda=\{k_1,k_2, \ldots, k_q\} of positive integers, let k_{\lambda} = \sum_{i=1}^q k_i. A \lambdalist assignment of G is a list assignment L of G such that the colour set \bigcup_{v \in V(G)}L(v) can be partitioned into the disjoint union C_1 \cup C_2 \cup \ldots \cup C_q of q sets so that for each i and each vertex v of G, L(v) \cap C_i \ge k_i. We say G is \lambdachoosable if G is Lcolourable for any \lambdalist assignment L of G. The concept of \lambdachoosability puts kcolourability and kchoosability in the same framework: If \lambda = \{k\}, then \lambdachoosability is equivalent to kchoosability; if \lambda consists of k copies of 1, then \lambdachoosability is equivalent to k colourability. If G is \lambdachoosable, then G is k_{\lambda}colourable. On the other hand, there are k_{\lambda}colourable graphs that are not \lambdachoosable, provided that \lambda contains an integer larger than 1. Let \phi(\lambda) be the minimum number of vertices in a k_{\lambda}colourable non\lambdachoosable graph. This paper determines the value of \phi(\lambda) for all \lambda. Keyphrases: \lambdalist assignment, chromaticchoosable graph, nonchromatic\lambdachoosable graph
