Home OALib Journal OALib PrePrints Submit Ranking News My Lib FAQ About Us Follow Us+ All Title Author Keywords Abstract
 Publish in OALib Journal ISSN: 2333-9721 APC: Only $99  Views Downloads  Relative Articles On List Colouring and List Homomorphism of Permutation and Interval Graphs 3-List Colouring Permutation Graphs List Colouring Big Graphs On-Line List Colouring Squares of Planar Graphs On-line list colouring of random graphs On Galvin orientations of line graphs and list-edge-colouring List edge-colouring and total colouring in graphs of low treewidth L- edge colouring of graphs Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs Frugal Colouring of Graphs More... Mathematics 2014 # Partial list colouring of certain graphs  Full-Text Cite this paper Abstract: 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 claw-free graphs, graphs with large chromatic number, chordless graphs, and series-parallel 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}\$.

Full-Text 