On \(t\)-common list-colorings (Q2401414): Difference between revisions

Summary: In this paper, we introduce a new variation of list-colorings. For a graph \(G\)~ and for a given nonnegative integer \(t\), a \(t\)-common list assignment of \(G\) is a mapping \(L\) which assigns each vertex \(v\) a set \(L(v)\) of colors such that given set of \(t\) colors belong to \(L(v)\) for every \(v\in V(G)\). The \(t\)-common list chromatic number of \(G\) denoted by \(ch_t(G)\) is defined as the minimum positive integer \(k\) such that there exists an \(L\)-coloring of \(G\) for every \(t\)-common list assignment \(L\) of \(G\), satisfying \(|L(v)| \geq k\) for every vertex \(v\in V(G)\). We show that for all positive integers \(k, \ell\) with \(2 \leq k \leq \ell\) and for any positive integers \(i_1 , i_2, \ldots, i_{k-2}\) with \(k \leq i_{k-2} \leq \cdots \leq i_1 \leq \ell\), there exists a graph \(G\) such that \(\chi(G)= k\), \(ch(G) =~ \ell\) and \(ch_t(G) = i_t\) for every \(t=1, \ldots, k-2\). Moreover, we consider the \(t\)-common list chromatic number of planar graphs. From the four color theorem and the result of \textit{C. Thomassen} [J. Comb. Theory, Ser. B 62, No. 1, 180--181 (1994; Zbl 0805.05023)], for any \(t=1\) or 2, the sharp upper bound of \(t\)-common list chromatic number of planar graphs is 4 or 5. Our first step on \(t\)-common list chromatic number of planar graphs is to find such a sharp upper bound. By constructing a planar graph \(G\) such that \(ch_1(G) =5\), we show that the sharp upper bound for 1-common list chromatic number of planar graphs is 5. The sharp upper bound of 2-common list chromatic number of planar graphs is still open. We also suggest several questions related to \(t\)-common list chromatic number of planar graphs.