On a conjecture of Erdős, Rubin and Taylor

Rok, strany: 1996, 69 - 82

A graph $G$ with vertex set $V$ and edge set $E$ is called $(a, b)$-choosable if for any assignment of lists $L(v)$ of colours to the vertices $v$ of $G$ with $|L(v)|=a$ it is possible to choose subsets $C(v)\subset L(v)$, $|C(v)|=b$ for every $v\in V$ such that $C(u)\cap C(v)=\emptyset$ for all $uv\in E$. In 1979, Erdős, Rubin and Taylor [P. Erdős, A. L. Rubin, H. Taylor: Choosability in graphs, Proceedings of the West Coast Conference on Combinatorics Graph Theory and Computing, Arcata, California, 1979, Congressus Numeratium 26 (1979), 125–157] raised the conjecture that every $(a, b)$-choosable graph $G$ is also $(am, bm)$-choosable for all $m>1$. We investigate the case $b=1$, presenting some classes of $(a, 1)$-choosable graphs for which $(am,m)$-choosability can be proved for all $m$.

ISO 690:

Tuza, Z., Voigt, M. 1996. On a conjecture of Erdős, Rubin and Taylor. In Tatra Mountains Mathematical Publications, vol. 9, no.3, pp. 69-82. 1210-3195.

APA:

Tuza, Z., Voigt, M. (1996). On a conjecture of Erdős, Rubin and Taylor. Tatra Mountains Mathematical Publications, 9(3), 69-82. 1210-3195.