Partial List Colouring of Certain Graphs

  • Jeannette Janssen
  • Rogers Mathew
  • Deepak Rajendraprasad
Keywords: Partial list colouring conjecture, claw-free graph, series-parallel graph, chordless graph, treewidth, choosability


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.
Article Number