  The Catalan numbers occur in various counting problems in combinatorics. This
paper reveals a connection between the Catalan numbers and list colouring of
graphs. Assume $G$ is a graph and $f:V(G) \to N$ is a mapping. For a
nonnegative integer $m$, let $f^{(m)}$ be the extension of $f$ to the graph $ G
\diamondplus \overline{K_m}$ for which $f^{(m)}(v)=|V(G)|$ for each vertex $v$
of $\overline{K_m}$. Let $m_c(G,f)$ be the minimum $m$ such that $ G
\diamondplus \overline{K_m}$ is not $f^{(m)}$-choosable and $m_p(G,f)$ be the
minimum $m$ such that $ G \diamondplus \overline{K_m}$ is not
$f^{(m)}$-paintable.
  We study the parameter $m_c(K_n, f)$ and $m_p(K_n,f)$ for arbitrary mappings
$f$.
  For $\vec{x}=(x_1,x_2,\ldots,x_n)$, an $\vec{x}$-dominated path ending at
$(a, b)$ is a monotonic path $P$ of the $a \times b$ grid from $(0,0)$ to
$(a,b)$ such that each vertex $(i,j)$ on $P$ satisfies $i \le x_{j+1}$.
  Let $\psi(\vec{x})$ be the number of $\vec{x}$-dominated paths ending at
$(x_n,n)$. By this definition, the Catalan number $C_n$ equals $ \psi((0,1,
\ldots, n-1)) $. This paper proves that if $G=K_n$ has vertices $v_1, v_2,
\ldots, v_n$ and $f(v_1) \le f(v_2) \le \ldots \le f(v_n)$, then
$m_c(G,f)=m_p(G,f)=\psi(\vec{x}(f))$, where $\vec{x}(f)=(x_1, x_2, \ldots,
x_n)$ and $x_i=f(v_i)-i$ for $i=1, 2,\ldots, n$. Therefore, if $f(v_i)=n$, then
$m_c(K_n, f)=m_p(K_n, f)$ equals the Catalan number $C_n$.
