\documentclass[12pt]{article} \usepackage{e-jc} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Packages and formatting %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Packages %\usepackage[margin=3cm]{geometry} \usepackage{xcolor} \usepackage{amsthm, amssymb, amsmath} \usepackage{enumerate} \usepackage{algorithmic} \usepackage{authblk} \usepackage{graphics} \usepackage{pstricks} \usepackage{subfigure} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} %% Formatting \renewcommand\Authfont{\small} \renewcommand\Affilfont{\itshape\small} \setcounter{Maxaffil}{0} % Hyperlinks \hypersetup{ colorlinks=false, linkcolor=red, citecolor=red, pdfborder={0 0 0}, } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Meta data %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{Partial list colouring of certain graphs} \author[1]{Jeannette Janssen} \author[2]{Rogers~Mathew\footnote{While this work was done, the author was an AARMS postdoctoral fellow in the Department of Mathematics and Statistics, Dalhousie University, Halifax, Canada - B3H 3J5.}} \author[3]{Deepak Rajendraprasad\footnote{While this work was done, the author was supported by a VATAT Postdoctoral Fellowship and the Israel Science Foundation (grant number 862/10).}} \affil[1] { Department of Mathematics and Statistics, \authorcr Dalhousie University, Halifax, Canada - B3H 3J5. \authorcr email: janssen@mathstat.dal.ca } \affil[2] { Department of Computer Science and Engineering, \authorcr Indian Institute of Technology, \authorcr Kharagpur 721302, West Bengal, India. \authorcr email: rogersmathew@gmail.com } \affil[3] { Department of Computer Science, \authorcr Caesarea Rothschild Institute, \authorcr University of Haifa, 31905 Haifa, Israel. \authorcr email: deepakmail@gmail.com } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Theorem like environments %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \theoremstyle{definition} \newtheorem{definition}{Definition} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{openproblem}[theorem]{Open problem} \newtheorem{observation}[theorem]{Observation} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{example}[theorem]{Example} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheoremstyle{plainitshape}% name of the style to be used {}% measure of space to leave above the theorem. E.g.: 3pt {}% measure of space to leave below the theorem. E.g.: 3pt {\itshape}% name of font to use in the body of the theorem {}% measure of space to indent {\itshape}% name of head font {.}% punctuation between head and body {0.5em}% space after theorem head {}% Manually specify head \theoremstyle{plainitshape} \newtheorem{property}{Property} \newtheorem{claim}{Claim}[theorem] \newtheoremstyle{cases}% name of the style to be used {}% measure of space to leave above the theorem. E.g.: 3pt {}% measure of space to leave below the theorem. E.g.: 3pt {}% name of font to use in the body of the theorem {}% measure of space to indent {}% name of head font {\newline}% punctuation between head and body {0.5em}% space after theorem head {{\itshape \thmname{#1}} \thmnumber{#2} ({\itshape\thmnote{#3}}).\medskip}% Manually specify head \theoremstyle{cases} \newtheorem{case}{Case} \newtheorem{subcase}{Sub-case}[case] \newtheoremstyle{constructions}% name of the style to be used {}% measure of space to leave above the theorem. E.g.: 3pt {}% measure of space to leave below the theorem. E.g.: 3pt {}% name of font to use in the body of the theorem {}% measure of space to indent {}% name of head font {}% punctuation between head and body {0.5em}% space after theorem head {{\itshape \thmname{#1}} \thmnumber{#2}\medskip}% Manually specify head \theoremstyle{constructions} \newtheorem{construction}{Construction}[theorem] % Highlights \newcommand{\doubt}[1]{{\color{red} #1}} \newcommand{\hide}[1]{{\color{yellow} #1}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Body %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} \date{} \maketitle \begin{abstract} The \emph{partial list colouring conjecture} due to Albertson, Grossman, and Haas \cite{albertson2000partial} 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. %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 \emph{$\mathcal{L}_k$-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 \emph{$k$-choosable} if for every such function $\mathcal{L}_k$, $G$ is $\mathcal{L}_k$-colourable. The minimum $k$ such that $G$ is $k$-choosable is called the \emph{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 \emph{partial list colouring conjecture} due to Albertson, Grossman, and Haas \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$-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 chromatic number at least $\frac{|V(G)|-1}{2}$, 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 connected $3$-choosable graphs where a largest induced $2$-choosable subgraph of each graph in the family is of size at most $\frac{5n}{8}$. \end{abstract} \section{Introduction} % Let $A$ be any set. For a positive integer $b$, where $ b \leq |A|$, we shall use $A \choose b$ to denote the collection of all $b$-sized subsets of $A$. Consider a simple, undirected, and finite graph $G$. Let $\mathcal{L} = \{l(v) : v \in V(G)\}$ denote an assignment of a list of admissible colours for each vertex in $G$. Then $G$ is \emph{$\mathcal{L}$-colourable} if there exists a proper colouring (i.e., no two adjacent vertices get the same colour) of the vertices of $G$ such that each vertex $v$ is assigned a colour from $l(v)$. If $|l(v)| = k$ for every $v \in V(G)$, then $\mathcal{L}$ is called a \emph{$k$-assignment}. We say $G$ is \emph{$k$-choosable} if $G$ is $\mathcal{L}$-colourable for all $k$-assignments $\mathcal{L}$. The \emph{list chromatic number} of $G$, denoted by $\chi_L(G)$, is the minimum positive integer $k$ such that $G$ is $k$-choosable. %Albertson et al. in \ref{} raised the following question: Consider a graph whose chromatic number is $s$. Take an $s$-colouring. We know that, for every positive integer $t$ less than $s$, one can properly colour at least $\frac{tn}{s}$ of its vertices using only $t$ colours (by taking the vertices of the largest $t$ colour classes of the $s$-colouring). Albertson, Grossman, and Haas in \cite{albertson2000partial} asked a similar and a very natural question on list colouring. Consider a graph $G$ on $n$ vertices whose list chromatic number is $s$. What if one assigns lists of size $t$ to each vertex where $t$ is some positive integer less than $s$? We know that with such a list assignment it may not be possible to list colour all the vertices of $G$. However, the question here is not to colour all the vertices but to colour as many vertices as one can. They conjectured that, given a $t$-assignment, one can always find an induced subgraph of order at least $\frac{tn}{s}$ that can be properly list coloured. We give a more formal description of the conjecture in the next paragraph. Consider an arbitrary graph $G$ on $n$ vertices whose list chromatic number is $s$. Let $t$ be a positive integer such that $1 \leq t \leq s$. Let $\mathcal{L}_t = \{l_t(v) : v \in V(G)\}$ be any $t$-assignment for $G$. Let $\lambda_{\mathcal{L}_t}(G)$ denote the order of a largest induced subgraph of $G$ that is $\mathcal{L}_t$-colourable. Let $\lambda_t(G) = \min\{\lambda_{\mathcal{L}_t}(G): \mathcal{L}_t \mbox{ is a }t\mbox{-assignment for }G\}$. \vspace{0.2in} \\ \textbf{Partial list colouring (PLC) conjecture} (Conjecture $1$ in \cite{albertson2000partial}): $\lambda_t(G) \geq \frac{tn}{s}$. \vspace{0.2in} \\ The authors in \cite{albertson2000partial} showed that $\lambda_t(G)$ is always at least $\left(1-(\frac{\chi(G)-1}{\chi(G)})^t\right)n$, where $\chi(G)$ denotes the chromatic number of $G$. For a bipartite graph this proves the conjecture as by induction one can see that $\left(1-(\frac{\chi(G)-1}{\chi(G)})^t\right)n \geq \frac{tn}{\chi(G) + t -1} = \frac{t}{t+1}n$. Chappell in \cite{chappell1999lower} showed that $\lambda_t(G)$ is lower bounded by $\frac{6}{7}\frac{tn}{s}$. Janssen in \cite{janssen2001partial} proved that the conjecture holds true for every graph whose list chromatic number is at least its maximum degree. Using a clever argument based on the pigeonhole principle, it was shown in \cite{haas2003bounds} that $\lambda_t(G) \geq \frac{n}{\lceil\frac{s}{t}\rceil}$. In addition to giving an alternate proof to this result, Iradmusa in \cite{iradmusa2010note} proved that either $\lambda_t(G) \geq \frac{tn}{s}$ or $\lambda_{s-t}(G) \geq \frac{(s-t)n}{s}$ i.e. the conjecture is true for at least half the number of different values of $t$. Apart from these initial results, to the best of our knowledge, no significant progress has been made so far towards settling the conjecture even with regard to special graph classes. Tuza, Kratochvil, and Voigt in their paper \cite{tuza1999new} surveying the then recent trends in colouring discuss the PLC conjecture. %The conjecture has also found its place in the list of open problems in `openproblemgarden' (http://www.openproblemgarden.org/op/partial\_list\_coloring). %the conjecture is true for at least half of the different values of $t$, where $t \in [s-1]$. \subsection{Our Contribution} In Section \ref{subsec:claw-free}, we prove that the PLC conjecture holds true for claw-free graphs. The complete bipartite graph $K_{1,3}$ is called a \emph{claw} and a \emph{claw-free} graph is a graph that does not have a claw as an induced subgraph. We know that the line graph (or the edge graph) of a graph is always claw-free. The famous \emph{list colouring conjecture} states that the chromatic number of the line graph (of a graph) is equal to its list chromatic number. Assume the list colouring conjecture is true. Let $G$ be the line graph of some graph. Let $G$ be $s$-choosable, and let $t \in [s]$. Since any induced subgraph of $G$ is also a line graph, choosing the subgraph induced on the vertices of the largest $t$ colour classes of any proper $s$-colouring of $G$ would give us a graph of order at least $\frac{t|V(G)|}{s}$ that is $t$-choosable, thus proving the PLC conjecture to be true in the context of line graphs. Hence, if the list colouring conjecture is true then the PLC conjecture is true for line graphs. The contrapositive of this statement is what motivated us to investigate the PLC conjecture in the context of claw-free graphs. Ohba's conjecture \cite{OhbaConjecture} states that, for a graph $G$ on $n$ vertices, if $\chi(G) \geq \frac{n-1}{2}$ then $\chi_L(G) = \chi(G)$. In the year 2012, this conjecture was settled in the affirmative by Noel, Reed, and Wu \cite{NoelReedWu}. Using this result, in Section \ref{subsec:large_chromatic_number}, we show that the PLC conjecture is also true for these graphs. A graph $G$ is \emph{$k$-degenerate} if the vertices of $G$ can be arranged on a horizontal line from left to right such that no vertex has more than $k$ neighbours to its right. From such an ordering of the vertices it's easy to see that if $G$ is $k$-degenerate then $\chi(G) \leq k+1$ and $\chi_L(G) \leq k + 1$. In particular, if $G$ is $2$-degenerate then $G$ is always $3$-choosable and $ \chi(G) \leq 3$. Since we know that the PLC conjecture is true (from Theorem $2$ in \cite{albertson2000partial}) for bipartite graphs, the interesting scenario is when $G$ is $2$-degenerate and $\chi(G) = 3$ (, and thereby $\chi_L(G)=3$). %Since $\chi_L(G) \geq \chi(G)$, this implies that the list chromatic number of $G$ is also $3$. Thus, investigating the PLC conjecture in the context of $2$-degenerate graphs is all about finding an answer to the following question: given any $2$-assignment for $G$, can we always find an induced subgraph of order $\frac{2|V(G)|}{3}$ that can be properly list coloured using the $2$-assignment? In Sections \ref{subsec:chordless} and \ref{Ser-Par-SubSec}, we find a positive answer to this question in the context of certain subclasses of $2$-degenerate graphs, namely chordless graphs, and series-parallel graphs. %In the subsections of Section \ref{ProofSection} of 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. Since line graphs are claw-free graphs, this means that the conjecture id true in the context of line graphs. %Further, we show that if $tw(G)$ denotes the treewidth of a graph $G$ then $\lambda_t(G) \geq \frac{tn}{tw(G)+1}$. %In the second part of the paper, i.e. in Section \ref{StrongerConjectureSection}, we deal with the question of finding a largest induced $t$-choosable subgraph in an $s$-choosable graph $G$ on $n$ vertices (, where $tr$, where $0 < r < s$. Consider the case when $t=r$. Let $R = \{c_1, \ldots , c_p\}$ be any set of colours such that $|R| \geq r$. Consider an arbitrary list assignment, say $l': V(G) \rightarrow {R \choose r}$, that assigns an $r$-sized list from $R$ to each vertex in $G$. For each $v \in V(G)$, we assign a list $l(v)$ which is defined as $l(v) = l'(v) \cup \{c_{\infty}\}$, where $c_{\infty} \notin R$. By induction hypothesis, there exists an induced subgraph $G_{r+1}$ of $G$ such that $|V(G_{r+1})| \geq \frac{(r+1)n}{s}$ and $G_{r+1}$ has a proper vertex colouring where each vertex $v$ is assigned a colour from $l(v)$. % \end{proof} Here we prove that the PLC conjecture holds true for all claw-free graphs. The proof technique is similar to the one used in \cite{janssen2001partial} to prove the conjecture for a graph whose list chromatic number is at least its maximum degree. Given a list assignment for a graph where the size of lists is smaller than required, we append every list with a set of new colours such that the new list size equals the list chromatic number of the graph. Next we do a proper list colouring of the graph using the new lists such that the number of vertices that are assigned a new colour is minimized. A simple counting argument is then used to prove that the above list colouring colours sufficient number of vertices using a colour from their original lists. \begin{theorem} Let $G$ be a claw-free graph on $n$ vertices whose list chromatic number is $s$. Then, for every $t \in [s]$, $\lambda_t(G) \geq \frac{tn}{s}$. \end{theorem} \begin{proof} %From Proposition \ref{InductiveRemark} we know that in order to prove the theorem it is enough to prove that every graph in the family of claw-free graphs satisfy Property $\mathcal{P}$. Let $\mathcal{L}_t = \{l_t(v)~:~v \in V(G)\}$ be an arbitrary $t$-assignment for $G$. Let $\bigcup_{v \in V(G)} l_t(v)$ $= \{1, \ldots , p\}$. Let $l_s(v) = l_t(v) \cup \{\sigma_1, \ldots , \sigma_{s-t}\}$, for every $v \in V(G)$. Let $\mathcal{L}_{s} = \{l_s(v)~:~v \in V(G)\}$. Since $\chi_L(G) = s$, $G$ is $\mathcal{L}_s$-colourable. %In order to prove that $G$ satisfies property $P$ we have to show that there exists an induced subgraph of $G$ of size at least $\frac{(s-1)n}{s}$ that is $l_{s-1}$-colourable. Let $f:V(G) \rightarrow \{1, \ldots, p, \sigma_1, \ldots ,$ $\sigma_{s-t}\}$ be an $\mathcal{L}_s$-colouring of $G$ such that the number of vertices that receive a colour from the set $\{\sigma_1, \ldots , \sigma_{s-t}\}$ is minimum. For each $i \in \{1, \ldots p, \sigma_1, \ldots , \sigma_{s-t} \}$, let $C_i := \{v \in V(G)~|~f(v) = i\}$ and let $V_i := \{v \in V(G)~|~i \in l_s(v)\}$. If $|C_{\sigma_1} \cup \cdots \cup C_{\sigma_{s-t}}| \leq \frac{(s-t)n}{s}$, then the theorem is proved. Suppose $|C_{\sigma_1} \cup \cdots \cup C_{\sigma_{s-t}}| > \frac{(s-t)n}{s}$. Then there exists some $i \in \{1, \ldots , s-t\}$ such that $|C_{\sigma_i}| > \frac{n}{s}$. For ease of notation, from now we shall use $\sigma$ to denote one such $\sigma_i$. Then, \begin{eqnarray} \label{ineq1} \sum_{i=1}^{p}|C_i| & < & \frac{tn}{s} \end{eqnarray} and \begin{eqnarray} \label{ineq2} \sum_{i=1}^{p}|C_{\sigma} \cap V_i| > \frac{tn}{s}. \end{eqnarray} From Inequalities (\ref{ineq1}) and (\ref{ineq2}), we can conclude that there exists some $j \in [p]$ such that $|C_j| < |C_{\sigma} \cap V_j|$. Let $X \subseteq C_{\sigma} \cap V_j$ such that $|N_G(X) \cap C_j| < |X|$ and, subject to this, $|N_G(X) \cap C_j|$ is minimized. %Find an $X \subseteq C_{\sigma} \cap V_j$ such that its neighbourhood in $C_j$ is minimum and is of a size smaller than $|X|$. %$|N_G(X) \cap C_j|$ is minimum and $|N_G(X) \cap C_j| < X$. The existence of such an $X$ is guaranteed by the presence of the set $C_{\sigma} \cap V_j$ whose neighbourhood in $C_j$ is smaller than itself in size. We claim that every vertex in $N_G(X) \cap C_j$ has at least two neighbours in $X$. Otherwise, if a vertex in the neighbourhood of $X$ in $C_j$ has only one or no neighbour in $X$ then we can remove such a vertex only to reduce the size of both $N_G(X) \cap C_j$ and $X$ by at most $1$. But this contradicts the minimality of $|N_G(X) \cap C_j|$. Hence every vertex in $N_G(X) \cap C_j$ has at least two neighbours in $X$. Since $G$ is claw-free and every vertex in $N_G(X) \cap C_j$ has at least two neighbours in $X$, no vertex in $N_G(X) \cap C_j$ has a neighbour in $C_{\sigma} \setminus X$. By assigning colour $j$ to vertices in $X$ and colour $\sigma$ to vertices in $N_G(X) \cap C_j$, one can find another valid $\mathcal{L}_s$-colouring of $G$ that has lesser number of vertices taking colours $\sigma_1, \ldots , \sigma_{s-t}$ as compared to $f$. This contradicts the property of $f$. % is an $\mathcal{L}_s$-colouring of $G$ that has the minimum number of vertices getting colours $\sigma_1, \ldots , \sigma_{s-t}$. %Hence, our assumption that $|C_{\sigma}| > \frac{n}{s}$ is wrong. % Thus, one can find another $l_s$ colouring of $G$ defined as: $f'(v) $f'(v) = f(v)$, otherwise. %We shall prove the theorem for $t=s-1$ by showing that we can do a proper vertex colouring of and induced subgraph $H$ % 5 of $G$ such that $|V(H)| \geq \frac{(s-1)n}{s}$ and every vertex $v$ in $H$ gets a colour from $l'(v)$. Let % 5$G_{r+1}$ be the induced subgraph of $G$ such that $|G_{r+1}| \geq \frac{(r+1)n}{s}$. \end{proof} %Since line graphs are claw-free graphs, we have the following corollary. %\begin{corollary} %Let $G$ be a line graph (of any multigraph) on $n$ vertices whose list chromatic number is $s$. Then for every positive integer $t$ less than $s$, $\lambda_t(G) \geq \frac{tn}{s}$. %\end{corollary} \subsection{Graphs with chromatic number at least \texorpdfstring{$\frac{|V(G)|-1}{2}$}{Lg}} \label{subsec:large_chromatic_number} %Ohba in \cite{OhbaConjecture} conjectured that, for a graph $G$, if $\chi(G) \geq \frac{|V(G)|-1}{2}$ then $\chi_L(G) = \chi(G)$. In 2012, the conjecture was settled in the affirmative by Noel, Reed, and Wu \cite{NoelReedWu}. The statement of the following theorem was a conjecture due to Ohba \cite{OhbaConjecture}. In 2012, the conjecture was settled in the affirmative by Noel, Reed, and Wu \cite{NoelReedWu}. \begin{theorem}[Noel, Reed, and Wu \cite{NoelReedWu}] \label{thm:OhbaNoel} For a graph $G$, if $\chi(G) \geq \frac{|V(G)|-1}{2}$ then $\chi_L(G) = \chi(G)$. \end{theorem} Theorem \ref{thm:largeChromatic} is a strengthening of the PLC conjecture on graphs with chromatic number at least $\frac{|V(G)|-1}{2}$. \begin{theorem} \label{thm:largeChromatic} Let $G$ be a graph with $\chi_L(G) = s$, and $\chi(G) \geq \frac{|V(G)|-1}{2}$. Then, for every $t \in [s]$, there is an induced subgraph, say $H_t$, of $G$ such that \\ (i) $\chi(H_t) \geq \frac{|V(H_t)| - 1}{2}$, \\ (ii) $\chi_L(H_t) = \chi(H_t) = t$, and \\ (iii) $|V(H_t)| \geq \frac{t|V(G)|}{s}$. \end{theorem} \begin{proof} We prove the lemma by a downward induction on $t$. When $t=s$, let $H_s = G$. Then, Conditions (i) and (iii) in the lemma are clearly true. By Theorem \ref{thm:OhbaNoel}, $\chi_L(H_s) = \chi(H_s) = s$. This proves the base case. %(by taking $H_s = G$) it is easy to see that the statement is true. Let $r \in [s-1]$. For the induction step, assume the statement of the lemma to be true for every $t$ greater than $r$ (with $t \leq s$). Let $t=r$. By the induction hypothesis, we have (i) $\chi(H_{t+1}) \geq \frac{|V(H_{t+1})| - 1}{2}$, (ii) $\chi_L(H_{t+1}) = \chi(H_{t+1}) = t+1$, and (iii) $|V(H_{t+1})| \geq \frac{(t+1)|V(G)|}{s}$. % Since $\chi(H_{t+1}) \geq \frac{|V(H_{t+1})|-1}{2}$, by Theorem \ref{thm:OhbaNoel}, we have $\chi_L(H_{t+1}) = \chi(H_{t+1}) = t+1$. Consider a proper vertex colouring of $H_{t+1}$ using $t+1$ colours. Let $C_1, \ldots , C_{t+1}$ be the $t+1$ colour classes of this colouring. If $t+1 > \frac{|V(H_{t+1})|}{2}$, then there exists some $C_i$ of size $1$. Let $H_t = H_{t+1} \setminus C_i$. We then have $\chi(H_{t}) = t > \frac{|V(H_{t+1})|}{2} - 1 = \frac{|V(H_{t})| - 1}{2}$ and therefore, by Theorem \ref{thm:OhbaNoel}, $\chi_L(H_t) = \chi(H_t) = t$. Note that $|V(H_{t})| = |V(H_{t+1})|-1 \geq \frac{(t+1)|V(G)|}{s}-1 \geq \frac{t|V(G)|}{s}$, since $|V(G)|$ is always at least $s$. %Consider any $i \in \{1, \ldots, s\}$. Suppose %$\left(\chi(H_{t+1})=\right)~ $t+1 \leq \frac{|V(H_{t+1})|}{2}$. %It is given that $s \geq \frac{n-1}{2}$. If, for some $a \in [t+1]$, $|C_a| = 2$ then let $H_{t} = H_{t+1} \setminus C_a$. Otherwise, since %$\frac{|V(H_{t+1})|}{2} \geq $\chi(H_{t+1}) \geq \frac{|V(H_{t+1})|-1}{2}$ there exist colour classes $C_b, C_c$ such that $|C_b|=1$ and $|C_c|>2$. Consider a vertex $u \in C_c$. If $\chi(H_{t+1} \setminus u) = t+1$, then let $H_{t} = H_{t+1} \setminus (C_b \cup \{u\})$. Otherwise, if $\chi(H_{t+1} \setminus u) = t$, then let $v \in C_c \setminus \{u\}$ %such that $v \neq u$ and let $H_{t} = H_{t+1} \setminus \{u,v\}$. Now consider the graph $H_{t}$. No matter how $H_{t}$ was constructed from $H_{t+1}$, we have $\chi(H_{t}) = t$ and $|V(H_{t})| = |V(H_{t+1})|-2$. We thus have $\chi(H_{t}) = t = (t+1) - 1 \geq \frac{|V(H_{t+1})|-1}{2} - 1 = \frac{|V(H_{t})| -1}{2}$. Hence, by Theorem \ref{thm:OhbaNoel}, $\chi_L(H_{t}) = \chi(H_{t}) = t$. Note that $|V(H_{t})| = |V(H_{t+1})| - 2 = \frac{t|V(H_{t+1})|}{t+1} + \frac{|V(H_{t+1})|}{t+1} - 2 \geq \frac{t|V(H_{t+1})|}{t+1}$, since $|V(H_{t+1})| \geq 2(t+1)$. Substituting $|V(H_{t+1})| \geq \frac{(t+1)|V(G)|}{s}$ in the above inequality, we get $|V(H_t)| \geq \frac{t|V(G)|}{s}$. \end{proof} \begin{corollary} \label{largeChromatCor} Let $G$ be a graph with $\chi_L(G) = s$, and $\chi(G) \geq \frac{|V(G)|-1}{2}$. Then, for every $t \in [s]$, $\lambda_t(G) \geq \frac{t|V(G)|}{s}$. \end{corollary} %\begin{theorem} %\label{largeChromatThm} %Let $G$ be a graph on $n$ vertices whose list chromatic number is $s$. Let $\chi(G) \geq \frac{n-1}{2}$. Then, for every positive integer $t$ less than $s$, $\lambda_t(G) \geq \frac{tn}{s}$. %\end{theorem} %\begin{proof} %%We know that $\chi_L(G) = \chi(G) = s$. Consider a proper vertex colouring of $G$. Let $G'$ be the subgraph induced on the vertices of the smallest $t$ colour classes of this colouring. Let $n' = |V(G')|$. Since $n' \leq \frac{tn}{s}$ and $n < 2s+1$, we have $\frac{n'-1}{2} \leq \frac{tn - s}{2s} < \frac{t(2s+1)-s}{2s} = \frac{(2t-1)s + t}{2s} = t - \frac{1}{2} + \frac{t}{2s} \leq t - \frac{1}{2} + \frac{s-1}{2s} \mbox{( since }t \mbox{ is at most } s-1) < t$. Thus $\chi(G') = t > \frac{n'-1}{2}$. Hence, by Theorem [] in \ref{}, %In the arguments to follow in the next two paragraphs, we shall show that $G$ always contains a subgraph $G'$ that is induced on some $n'$ vertices of $G$ such that $\chi_L(G') = s-1$, $|V(G')| = n' \geq \frac{(s-1)n}{s}$, and $\chi(G') \geq \frac{|V(G')| - 1}{2}$. By treating the new graph $G'$ as your graph $G$ and $s'$ as your $s$, one can revisit the arguments given in the two paragraphs to obtain another graph, say $G''$, such that $\chi_L(G'') = s-2$, $|V(G'')| \geq \frac{(s-2)n}{s}$, and $\chi(G'') \geq \frac{|V(G'')| - 1}{2}$. Extending this approach we can show that, for any positive integer $t$ less than $s$, $G$ always contains a subgraph $H$ that is induced on some $n_H$ vertices of $G$ such that $\chi_L(H) = t$, $|V(H)| = n_H \geq \frac{tn}{s}$, and $\chi(H) \geq \frac{|V(H)| - 1}{2}$ thus proving the conjecture. % %%$\lambda_t(G) \geq \frac{tn}{s}$. %% In this manner, we can show that %%Thus, $\lambda_{s-1}(G) \geq \frac{(s-1)n}{s}$. By replacing $G$ with $G'$, $s$ with $s'$ %% %%We shall prove the theorem when $t=s-1$. Extending the same argument gives a proof for any $t$. The idea of the proof is to find an induced subgraph $G'$ of $G$ such that $\chi_L(G') = s-1$ and $|V(G')| \geq \frac{(s-1)n}{s}$. %%If $G$ is a complete graph, then we know that the statement of the theorem is trivially true (it also follows from Observation \ref{}). Suppose $G$ is not a complete graph. % % %Since $\chi(G) \geq \frac{n-1}{2}$, from the result in \cite{NoelReedWu}, we know that $\chi_L(G) = \chi(G) = s$. Consider a proper vertex colouring of $G$ using $s$ colours. Let $C_1, \ldots , C_s$ be the $s$ colour classes of this colouring. If $s > \frac{n}{2}$, then there exists some $C_i$ of size $1$. Let $G' = G \setminus C_i$. We then have $\chi(G') = s-1 > \frac{n}{2} - 1 \geq \frac{|V(G')| - 1}{2}$ and therefore, by the result in \cite{NoelReedWu}, $G'$ is $(s-1)$-choosable. Note that $|V(G')| = n-1 \geq \frac{(s-1)n}{s}$, since $n$ is always at least $s$. %%Consider any $i \in \{1, \ldots, s\}$. % %Suppose $\chi(G) = s \leq \frac{n}{2}$. %%It is given that $s \geq \frac{n-1}{2}$. %If, for some $a \in \{1, \ldots ,s\}$, $|C_a| = 2$ then let $G' = G \setminus C_a$. Otherwise, since $\frac{n}{2} \geq \chi(G) \geq \frac{n-1}{2}$ there exist colour classes $C_b, C_c$ such that $|C_b|=1$ and $|C_c|>2$. Consider a vertex $u \in C_c$. If $\chi(G \setminus u) = s$, then let $G' = G \setminus C_b \cup \{u\}$. Otherwise, if $\chi(G \setminus u) = s-1$ then let $v$ be a vertex other than $u$ present in $C_c$ and let $G' = G \setminus \{u,v\}$. Now consider the graph $G'$. No matter how $G'$ was constructed from $G$, we have $\chi(G') = s-1$ and $|V(G')| = n-2$. We thus have $\chi(G') = s-1 \geq \frac{n-1}{2} - 1 = \frac{|V(G')| -1}{2}$. Hence, by the result in \cite{NoelReedWu}, $\chi_L(G') = \chi(G') = s-1$. Note that $|V(G')| = n-2 \geq \frac{(s-1)n}{s}$ since $n$ is at least $2s$. % % %%Let $G'$ be the subgraph induced on the vertices of the largest $s-1$ colour classes of this colouring. Clearly, $|V(G')| \geq \frac{(s-1)n}{s}$ and $|V(G) \setminus V(G')| \geq 1$. That is, $s-1 \geq \frac{n-1}{2}-1 = \frac{n-3}{2} \frac{|V(G')|-1}{2} \leq \frac{n-3}{2} = \frac{n-1}{2} - 1 < s-1$. Hence, by Theorem [] in \ref{}, $\chi_L(G') = s-1$. %\end{proof} \subsection{Chordless graphs} \label{subsec:chordless} A graph $G$ is \emph{chordless} if no cycle in $G$ has a chord. Further, $G$ is \emph{minimally $2$-connected} if $G$ is $2$-connected and chordless. Any graph obtained from a given graph by subdividing every edge of the given graph at least once is an example of a chordless graph. If the given graph is $2$-connected, then the resultant graph is minimally $2$-connected. %Chordless graphs are $2$-degenerate and therefore $3$-choosable. The following lemma about minimally $2$-connected graphs is due to Plummer \cite{plummer1968minimal}. \begin{lemma}[Plummer, \cite{plummer1968minimal}] \label{partitionlemma} Let $G$ be a $2$-connected graph. Then $G$ is minimally $2$-connected if and only if either \begin{itemize} \item $G$ is a cycle; or \item if $S$ denotes the set of nodes of degree $2$ in $G$, then $G\setminus S$ is a forest with at least two components. \end{itemize} \end{lemma} We use this lemma to prove the following. \begin{lemma} \label{degreeLemma} Let $G$ be a minimally $2$-connected graph. % Then for all $x \in V(G)$ there exist two vertices $v$ and $w$, each of degree $2$, in the neighbourhood of some vertex $u$ such that $x \notin \{v,w\}$. %Then $\forall x \in V(G)$, $\exists u,v,w \in V(G)$ such that $v,w \in N_G(u)$, $deg_G(v) = deg_G(w) = 2$, and $x \notin \{v,w\}$. Then, for every $x \in V(G)$, there exist two distinct vertices $v,w \in V(G) \setminus \{x\}$ and a vertex $u \in V(G)$ such that $v,w \in N_G(u)$ and $deg_G(v) = deg_G(w) = 2$. \end{lemma} \begin{proof} Consider any $x \in V(G)$. If $G$ is a cycle, then let $u = x$. Clearly, $u$ has two neighbours of degree $2$ none of which is $x$. Suppose $G$ is not a cycle. Then, by Lemma \ref{partitionlemma}, $G \setminus S$ is a forest with at least $2$ components, where $S$ is the set of nodes of degree $2$ in $G$. If $G \setminus S$ has any isolated vertex, then it has at least $3$ neighbours in $S$ (each of degree $2$) as each vertex outside $S$ has a degree at least $3$. Let the isolated vertex be our vertex $u$. Clearly, $u$ has two neighbours each of degree $2$ in its neighbourhood such that none of them is $x$. Suppose $G \setminus S$ does not contain any isolated vertex. We know that $G \setminus S$ contains at least two trees, say $T_1$ and $T_2$, by Lemma \ref{partitionlemma}. Let $l_1^1$ and $l_2^1$ be two leaf vertices of $T_1$. Similarly, let $l_1^2$ and $l_2^2$ be two leaf vertices of $T_2$. For all $i,j \in \{1,2\}$, since $l_i^j$ has degree at least $3$ in $G$, it has at least $2$ neighbours (each of degree $2$) in $S$. What is left is to show that, for some $i,j \in \{1,2\}$, $l_i^j$ ($=u$) has two neighbours each of degree $2$ in $S$ such that none of the two neighbours is $x$. Since every vertex of $S$ has its degree equal to $2$ in $G$, no three vertices in $G\setminus S$ can have the same neighbour in $S$. Since $l_i^j$ form a collection of four vertices, there exists one vertex in this collection (which forms the vertex $u$) such that it has two neighbours of degree $2$ none of which is $x$. \end{proof} %\begin{lemma} %Let $G$ be a chordless graph. Then, there always exist vertices $u,v$ and $w$ in $G$ such that $v,w \in N_G(u)$ and %\end{lemma} It is a known fact that chordless graphs are $2$-degenerate. For the sake of completeness, we prove this statement below. \begin{proposition} \label{prop:2degen} Let $G$ be a chordless graph. Then, $G$ is $2$-degenerate. \end{proposition} \begin{proof} We prove this by an induction on $|V(G)|$. The proposition is trivially true when $|V(G)| \leq 3$. Assume the proposition is true for every value of $|V(G)|$ less than $n$, where $n \geq 4$. Let $|V(G)| = n$. Suppose $G$ contains a vertex, say $v$, of degree at most $2$. Every induced subgraph of $G$ is also chordless. By induction hypothesis, $G \setminus v$ is $2$-degenerate. Therefore, $G$ is $2$-degenerate. Suppose every vertex in $G$ has degree at least $3$. Consider the block graph of $G$ and consider a leaf block $B$ in it. Since every vertex in $G$ is of degree at least $3$, $B$ is $2$-connected. Moreover, since $G$ is a chordless graph $B$ is minimally $2$-connected. Let $x \in V(B)$ be the cut vertex whose removal separates $B$ from rest of the graph. By Lemma \ref{degreeLemma}, there exists a vertex $v \in V(B) \setminus \{x\}$ such that $deg_B(v) = 2$. Since $v$ is not a cut vertex and since $B$ is a leaf block, we have $deg_G(v) = 2$. By induction hypothesis, $G \setminus v$ is $2$-degenerate. Therefore, $G$ is $2$-degenerate. \end{proof} \begin{theorem} Let $G$ be a chordless graph on $n$ vertices whose list chromatic number is $s$. Then, for every $t \in [s]$, $\lambda_t(G) \geq \frac{tn}{s}$. \end{theorem} \begin{proof} % Let $R = \{1, \ldots , p\}$ be any set of colours such that $|R| \geq s$. Consider an arbitrary list assignment, say $l_{s-1}: V(G) \rightarrow {R \choose (s-1)}$, that assigns an $(s-1)$-sized list from $R$ to each vertex in $G$. From Proposition \ref{prop:2degen}, we know that $G$ is $2$-degenerate. Therefore, $s \leq 3$. %Since every chordless graph is $2$-degenerate, $s \leq 3$. It is easy to see that the theorem is trivially true when $s \leq 2$. Assume $s =3$. We know that, when $t=1$, $\lambda_1(G) \geq \frac{n}{3}$ since the largest independent set in $G$ is of size at least $\frac{n}{3}$. Let $t=2$. In rest of the proof, using an induction on $n$, we show that $\lambda_2(G) \geq \frac{2n}{3}$. %It is easy to see that for every chordless graph on $1$, $2$, or $3$ vertices, the statement of the theorem holds. Suppose $G$ contains a vertex $v$ of degree at most $1$. By induction hypothesis, $\lambda_2(G \setminus v) \geq \frac{2(n-1)}{3}$. Since $v$ has only one neighbour in $G$, we can add back $v$ to $G \setminus v$ and colour $v$ with a colour in its list that does not conflict with its neighbour's colour. Thus, $\lambda_2(G) \geq \frac{2n}{3}$. Suppose every vertex in $G$ is of degree at least $2$. Consider the block graph of $G$ and consider a leaf block $B$ in it. Since every vertex in $G$ is of degree at least $2$, $B$ is $2$-connected. Moreover, since $G$ is a chordless graph $B$ is minimally $2$-connected. Let $x \in V(B)$ be the cut vertex whose removal separates $B$ from rest of the graph. By Lemma \ref{degreeLemma}, there exist two distinct vertices $v,w \in V(B) \setminus \{x\}$ and a vertex $u \in V(B)$ such that $v,w \in N_B(u)$ and $deg_B(v) = deg_B(w) = 2$. %$\exists u,v,w \in V(B)$ such that $v,w \in N_B(u)$, $x \notin \{v,w\}$, and $deg_B(v) = deg_B(w) = 2$. Since neither $v$ nor $w$ is a cut vertex, their degrees in $G$ remain the same, i.e., $deg_G(v) = deg_G(w) = 2$. Now, let $S = \{u,v,w\}$. By induction hypothesis, $\lambda_2(G \setminus S) \geq \frac{2(n-3)}{3}$. %Consider a partial list colouring of $G \setminus S$ us Consider adding $u,v$ and $w$ back in $G \setminus S$. It is easy to see that if we don't colour vertex $u$, then both $v$ and $w$ have at most one of their neighbours coloured and therefore can be properly coloured using a colour from their respective lists. Thus, $\lambda_2(G) \geq \frac{2(n-3)}{3} + 2 = \frac{2n}{3}$. \end{proof} \subsection{Series-parallel graphs} \label{Ser-Par-SubSec} A connected \emph{series-parallel} graph is a graph with two designated vertices $s$ and $t$ and the graph can be turned into a $K_2$ by a sequence of the following operations: (a) Replacement of a pair of edges with a single edge that connects their endpoints, and (b) Replacement of a pair of edges incident to a vertex of degree $2$ other than $s$ or $t$ with a single edge. Note that outerplanar graphs are series-parallel. From the definition, it is easy to see that series-parallel graphs are $2$-degenerate and therefore $3$-choosable. Hence, in order to prove the PLC conjecture for a series-parallel graph $G$ on $n$ vertices, it is enough to show that $\lambda_2(G) \geq \frac{2n}{3}$. We prove this by using the fact that series-parallel graphs are precisely the class of graphs with treewidth at most $2$. Before we prove this result, let us explore the connection between the treewidth of a graph $G$ and $\lambda_t(G)$. A graph family $\mathcal{G}$ is called a \emph{hereditary graph family} if it is closed under induced subgraphs. For example, the families of planar graphs, forests, chordal graphs etc. are hereditary graph families. \begin{proposition} \label{chromaticProp} Let $\mathcal{G}$ be a hereditary graph family. If, for every graph $G \in \mathcal{G}$, $\chi(G) = \chi_L(G)$ then for every $t$, where $0 < t \leq \chi_L(G)$, $\lambda_t(G) \geq \frac{tn}{\chi_L(G)}$. \end{proposition} \begin{proof} The proof is straightforward. Consider a graph $G \in \mathcal{G}$. Let $\chi_L(G) = \chi(G) = s$. Remove the vertices belonging to the smallest $s-t$ colour classes in a proper $s$-colouring of $G$ to obtain a graph $G'$ of order at least $\frac{tn}{s}$. Since $G'\in \mathcal{G}$, $\chi_L(G') = \chi(G') = t$. \end{proof} A graph is \emph{chordal} if it does not contain any induced cycle of size greater than $3$. Note that chordal graphs form a hereditary family of graphs. Moreover, for every chordal graph $G$, $\chi(G)=\chi_L(G)=\omega(G)$ (clique number). Since chordal graphs satisfy the conditions given in Proposition \ref{chromaticProp}, we have the following corollary. \begin{corollary} \label{chordalCorollary} Let $G$ be a chordal graph on $n$ vertices whose list chromatic number is $s$. Then, for every $t \in [s]$, $\lambda_t(G) \geq \frac{tn}{s}$. \end{corollary} A \emph{tree decomposition} of a graph $G$ is a pair $(\{X_i : i \in I\}, T)$, where $I$ is an index set, $\{X_i : i \in I\}$ is a collection of subsets of $V(G)$, and $T$ is a tree on $I$ such that \begin{enumerate}[(i)] \item $\bigcup_{i \in I} X_i = V(G)$, \item $\forall \{u, v\} \in E(G), \exists i \in I$ such that $u, v \in X_i$, and \item $\forall i, j, k \in I$: if $j$ is on the path in $T$ from $i$ to $k$, then $X_i \cap X_k \subseteq X_j$. \end{enumerate} The {\em width} of a tree decomposition $(\{X_i~:~i \in I\}, T)$ is $\max_{i \in I} |X_i| -1$. The \emph{treewidth} of $G$ is the minimum width over all tree decompositions of $G$ and is denoted by $tw(G)$. It is known that the treewidth of a graph $G$ is one less than the order of a largest clique in the chordal graph containing $G$ with the smallest clique number. The corollary below relates $\lambda_t(G)$ with the treewidth of $G$. \begin{corollary} \label{twCorollary} Let $G$ be a graph on $n$ vertices whose list chromatic number is $s$. Then, for every $t \in [s]$, $\lambda_t(G) \geq \frac{tn}{tw(G) + 1}$. \end{corollary} \begin{proof} Let $G'$ be a chordal graph obtained by adding edges to $G$ such that the order of a largest clique in $G'$, denoted by $\omega(G')$, is $tw(G)+1$. Since $tw(G)+1 = \omega(G')=\chi(G') = \chi_L(G')$, from Corollary \ref{chordalCorollary}, we get $\lambda_t(G') \geq \frac{tn}{tw(G) + 1}$. As $G$ is a subgraph of $G'$, any proper colouring of $G'$ is a proper colouring for $G$ as well. Thus we get $\lambda_t(G) \geq \frac{tn}{tw(G) + 1}$. \end{proof} The following result on series-parallel graphs follows directly from Corollary \ref{twCorollary}. \begin{corollary} Let $G$ be a series-parallel graph on $n$ vertices whose list chromatic number is $s$. Then, for every $t \in [s]$, $\lambda_t(G) \geq \frac{tn}{s}$. \end{corollary} %\section{$2$-choosable graphs in $3$-choosable graphs} %\label{StrongerConjectureSection} %In this section, we put forth a question which is a (stronger) variant of the partial list colouring conjecture. %Given a graph $G$ on $n$ vertices with list chromatic number $s$, for any positive integer $t