List colouring of graphs and generalized Dyck paths

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}$forwhich$f^{(m)}(v)=|V(G)|$foreachvertex$v$of$\overline{K_m}$\mathrm{.}Let$m_c(G,f)$betheminimum$m$suchthat$ G \diamondplus \overline{K_m}$isnot$f^{(m)}$-choosableand$m_p(G,f)$ be the minimum $m$ such that $G\text{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,\dots ,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)) $\mathrm{.}Thispaperprovesthatif$G=K_n$hasvertices$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$\mathrm{.}Therefore,if$f(v_i)=n$,then$m_c(K_n, f)=m_p(K_n, f)$equalstheCatalannumber$C_n$.