
Mathematics 2014
Partial list colouring of certain graphsAbstract: Let $G$ be a graph on $n$ vertices and let $\mathcal{L}_k$ be an arbitrary function that assigns each vertex in $G$ a list of $k$ colours. Then $G$ is $\mathcal{L}_k$list colourable if there exists a proper colouring of the vertices of $G$ such that every vertex is coloured with a colour from its own list. We say $G$ is $k$choosable if for every such function $\mathcal{L}_k$, $G$ is $\mathcal{L}_k$list colourable. The minimum $k$ such that $G$ is $k$choosable is called the list chromatic number of $G$ and is denoted by $\chi_L(G)$. Let $\chi_L(G) = s$ and let $t$ be a positive integer less than $s$. The partial list colouring conjecture due to Albertson et al. \cite{albertson2000partial} states that for every $\mathcal{L}_t$ that maps the vertices of $G$ to $t$sized lists, there always exists an induced subgraph of $G$ of size at least $\frac{tn}{s}$ that is $\mathcal{L}_t$list colourable. In this paper we show that the partial list colouring conjecture holds true for certain classes of graphs like clawfree graphs, graphs with large chromatic number, chordless graphs, and seriesparallel graphs. In the second part of the paper, we put forth a question which is a variant of the partial list colouring conjecture: does $G$ always contain an induced subgraph of size at least $\frac{tn}{s}$ that is $t$choosable? We show that the answer to this question is not always `yes' by explicitly constructing an infinite family of $3$choosable graphs where a largest induced $2$choosable subgraph of each graph in the family is of size at most $\frac{5n}{8}$.
