List colouring of graphs and generalized Dyck paths

DOI10.1016/J.DISC.2017.11.022MaRDI QIDQ1690249zbMATH OpenOpenAlexFDO

Authors Rongxing Xu, Yeong-Nan Yeh, Xuding Zhu

Publication date 19 January 2018

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.02852

zbMATH Keywords

generalized Dyck pathjoin of graphslist colouringonline list colouringpainting game

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30) Paths and cycles (05C38) Graph operations (line graphs, products, etc.) (05C76)

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)oN$ is a mapping. For a nonnegative integer $m$, let $f^{(m)}$ be the extension of $f$ to the graph $Gdiamondplusoverline{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 $Gdiamondplusoverline{K}_m$ is not $f^{(m)}$-choosable and $m_p(G,f)$ be the minimum $m$ such that $Gdiamondplusoverline{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 $vecx=(x_1,x_2,ldots,x_n)$, an $vecx$-dominated path ending at $(a,b)$ is a monotonic path $P$ of the $aimesb$ grid from $(0,0)$ to $(a,b)$ such that each vertex $(i,j)$ on $P$ satisfies $ile{x}_{j+1}$. Let $psi(vecx)$ be the number of $vecx$-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)lef(v_2)leldotslef(v_n)$, then $m_c(G,f)=m_p(G,f)=psi(vecx(f))$, where $vecx(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$.

Recommendations

• On the number of list‐colorings
• Path choosability of planar graphs
• Introduction to list colourings
• Generalized list colourings of graphs
• On generalized list colourings of graphs

Cites work

• Graph colorings with local constraints -- a survey
• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• scientific article; zbMATH DE number 3712896 (Why is no real title available?)
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 3563170 (Why is no real title available?)
• Mr. Paint and Mrs. Correct
• On-line list colouring of graphs
• Three topics in online list coloring
• Towards an on-line version of Ohba's conjecture

Cited in

(2)

• Generalized list \(T\)-colorings of cycles
• (2+ )-nonrepetitive list colouring of paths

This page was built for publication: List colouring of graphs and generalized Dyck paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1690249)