Online List Colorings with the Fixed Number of Colors

Abstract

The online list coloring is a widely studied topic in graph theory. A graph $G$ is 2-paintable if we always have a strategy to complete a coloring in an online list coloring of $G$ in which each vertex has a color list of size 2. In this paper, we focus on the online list coloring game in which the number of colors is known in advance. We say that $G$ is $[2,t]$-paintable if we always have a strategy to complete a coloring in an online list coloring of $G$ in which we know that there are exactly $t$ colors in advance, and each vertex has a color list of size 2. Let $M(G)$ denote the maximum $t$ in which $G$ is not $[2,t]$-paintable, and $m(G)$ denote the minimum $t\ge 2$ in which $G$ is not $[2,t]$-paintable. We show that if $G$ is not 2-paintable, then $2\le m(G)\le 4,$ and $n\le M(G)\le 2n-3.$ Furthermore, we characterize $G$ with $m(G)\in \{2,3,4\}$ and $M(G)\in \{n,n+1,2n-3\},$ respectively.