Minimum non-chromatic-\lambda-choosable graphs

arXiv2208.02050MaRDI QIDQ6406854FDOQ6406854

Authors: Jialu Zhu, Xuding Zhu 

Publication date: 3 August 2022

Abstract: For a multi-set $lambda=k_1,k_2,ldots,k_q$ of positive integers, let $k_{lambda}=su{m}_{i=1}^q{k}_i$. A $lambda$-list assignment of $G$ is a list assignment $L$ of $G$ such that the colour set $$ can be partitioned into the disjoint union $C_{1}cup{C}_{2}cupldotscup{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$.

This page was built for publication: Minimum non-chromatic-$\lambda$-choosable graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6406854)