List colouring of graphs and generalized Dyck paths

Abstract

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,\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,\dots ,n-1))$. This paper proves that if $G=K_n$ has vertices $v_1,v_2,\dots ,v_n$ and $f(v_1)\le f(v_2)\le \dots \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,\dots ,x_n)$ and $x_i=f(v_i)-i$ for $i=1,2,\dots ,n$. Therefore, if $f(v_i)=n$, then $m_c(K_n,f)=m_p(K_n,f)$ equals the Catalan number $C_n$.

16 pages, 3 figures