Minimum Non-Chromatic-λ-Choosable Graphs

EasyChair Preprint 10311

Abstract

For a multi-set \lambda=\{k_1,k_2, \ldots, k_q\} of positive integers, let k_{\lambda} = \sum_{i=1}^q k_i. A \lambda-list 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 \lambda-choosable if G is L-colourable for any \lambda-list assignment L of G. The concept of \lambda-choosability puts k-colourability and k-choosability in the same framework: If \lambda = \{k\}, then \lambda-choosability is equivalent to k-choosability; if \lambda consists of k copies of 1, then \lambda-choosability is equivalent to k -colourability. If G is \lambda-choosable, then G is k_{\lambda}-colourable. On the other hand, there are k_{\lambda}-colourable graphs that are not \lambda-choosable, provided that \lambda contains an integer larger than 1. Let \phi(\lambda) be the minimum number of vertices in a k_{\lambda}-colourable non-\lambda-choosable graph. This paper determines the value of \phi(\lambda) for all \lambda.

Keyphrases: \lambda-list assignment, chromatic-choosable graph, non-chromatic-\lambda-choosable graph

@booklet{EasyChair:10311,
  author    = {Jialu Zhu and Xuding Zhu},
  title     = {Minimum Non-Chromatic-λ-Choosable Graphs},
  howpublished = {EasyChair Preprint 10311},
  year      = {EasyChair, 2023}}