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)→N is a mapping. For a nonnegative integer m, let f(m) be the extension of f to the graph G Km¯ for which f(m)(v)=|V(G)| for each vertex v of Km¯. Let mc(G,f) be the minimum m such that G Km¯ is not f(m)-choosable and mp(G,f) be the minimum m such that G Km¯ is not f(m)-paintable. We study the parameter mc(Kn,f) and mp(Kn,f) for arbitrary mappings f. For x→=(x1,x2,…,xn), an x→-dominated path ending at (a,b) is a monotonic path P of the a×b grid from (0,0) to (a,b) such that each vertex (i,j) on P satisfies i≤xj+1. Let ψ(x→) be the number of x→-dominated paths ending at (xn,n). By this definition, the Catalan number Cn equals ψ((0,1,…,n−1)). This paper proves that if G=Kn has vertices v1,v2,…,vn and f(v1)≤f(v2)≤…≤f(vn), then mc(G,f)=mp(G,f)=ψ(x→(f)), where x→(f)=(x1,x2,…,xn) and xi=f(vi)−i for i=1,2,…,n. Therefore, if f(vi)=n, then mc(Kn,f)=mp(Kn,f) equals the Catalan number Cn. We also show that if G=G1∪G2∪⋯∪Gp is the disjoint union of graphs G1,G2,…,Gp and f=f1∪f2∪⋯∪fp, then mc(G,f)=∏i=1pmc(Gi,fi) and mp(G,f)=∏i=1pmp(Gi,fi). This generalizes a result in Carraher et al. (2014), where the case each Gi is a copy of K1 is considered.