کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903096 | 1632401 | 2018 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
List colouring of graphs and generalized Dyck paths
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: List colouring of graphs and generalized Dyck paths List colouring of graphs and generalized Dyck paths](/preview/png/8903096.png)
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 341, Issue 3, March 2018, Pages 810-819
Journal: Discrete Mathematics - Volume 341, Issue 3, March 2018, Pages 810-819
نویسندگان
Rongxing Xu, Yeong-Nan Yeh, Xuding Zhu,