Attainability of the Chromatic Number of Functigraphs

摘要

Let $G'$ be a copy of a graph $G$ and let $f: V(G) to V(G')$ be a function. A functigraph, denoted by $C(G,f)$, is a graph with $V(C(G,f)) = V(G)cup V(G')$ and $E(C(G,f)) = E(G)cup E(G')cup {uv: uin V(G), vin V(G'), v=f(u)}$. Let $chi(G)$ be the chromatic number of a graph. Recently, textit{Chen et al.} proved that $chi(G) leq chi(C(G,f)) leq leftlceil frac{3}{2} chi(G) rightrceil.$ In this paper we investigate the attainability of the chromatic numbers of functigraphs. We prove that for any two positive integers $a$ and $b$ with $a leq b leq leftlceil frac{3}{2}a rightrceil$, there exists a graph $G$ and function $f$ on $V(G)$ such that $chi(G)=a$ and $chi(C(G,f))=b$. We also characterize functions to determine the values of $chi(C(G,f))$ for all bipartite graphs and odd wheels. We finally provide some sufficient conditions on $f$ to have $chi(C(G, f)) = chi(G)$.