The strong fractional choice number and the strong fractional paint number of graphs

Abstract

This paper studies the strong fractional choice number $c{h}_f^s(G)$ and the strong fractional paint number ${\chi }_{f,P}^s(G)$ of a graph $G$. We prove that these parameters of any finite graph are rational numbers. On the other hand, for any positive integers $p,q$ satisfying $2\le \frac{2p}{2q+1}\le \lfloor \frac{p}{q}\rfloor$, there exists a graph $G$ with $c{h}_f^s(G)={\chi }_{f,P}^s(G)=\frac{p}{q}$. The relationship between ${\chi }_{f,P}^s(G)$ and $c{h}_f^s(G)$ is explored. We prove that the gap ${\chi }_{f,P}^s(G)-c{h}_f^s(G)$ can be arbitrarily large. The strong fractional choice number of a family $\mathcal{G}$ of graphs is the supremum of the strong fractional choice number of graphs in $\mathcal{G}$. Let $\mathcal{P}$ denote the class of planar graphs and ${\mathcal{P}}_{k_1,\dots ,k_q}$ denote the class of planar graphs without $k_i$-cycles for $i=1,\dots ,q$. We prove that $3+\frac{1}{2}\le c{h}_f^s({\mathcal{P}}_4)\le 4$, $c{h}_f^s({\mathcal{P}}_k)=4$ for $k\in \{5,6\}$, $3+\frac{1}{12}\le c{h}_f^s({\mathcal{P}}_{4,5})\le 4$ and $c{h}_f^s(\mathcal{P})\ge 4+\frac{1}{3}$. The last result improves the lower bound $4+\frac{2}{9}$ in [X. Zhu, multiple list colouring of planar graphs, Journal of Combin. Th. Ser. B,122(2017),794-799].

20 pages,6 figures

References in corpus (1)

• Chip games and paintability