Partial List Colouring of Certain Graphs

Jeannette Janssen, Rogers Mathew, Deepak Rajendraprasad

Abstract


The partial list colouring conjecture due to Albertson, Grossman, and Haas (2000) states that for every $s$-choosable graph $G$ and every assignment of lists of size $t$, $1 \leq t \leq s$, to the vertices of $G$ there is an induced subgraph of $G$ on at least $\frac{t|V(G)|}{s}$ vertices which can be properly coloured from these lists. In this paper, we show that the partial list colouring conjecture holds true for certain  classes of graphs like claw-free graphs, graphs with chromatic number at least $\frac{|V(G)|-1}{2}$, chordless graphs, and series-parallel graphs.

Keywords


Partial list colouring conjecture; claw-free graph; series-parallel graph; chordless graph; treewidth; choosability

Full Text: PDF