Facebook Instagram Twitter RSS Feed PodBean Back to top on side

Fractional $P$-colourings and $P$-choice-ratio

In: Tatra Mountains Mathematical Publications, vol. 18, no. 4
Peter Mihók - Zsolt Tuza - Margit Voigt
Detaily:
Rok, strany: 1999, 69 - 77
O článku:
The choice ratio of a graph $G=(V,E)$ is the minimum quotient $a/b$ with the following property. For every assignment of $a$-element sets $L(v)$ to the vertices $vin V$, there can be chosen $b$-element subsets $C(v)subset L(v)$ for all $v$ in such a way that $C(v)cap C(v')=emptyset$ holds for every adjacent vertex pair $v,v'$. Alon, Tuza and Voigt in [N. Alon, Zs. Tuza, M. Voigt: Choosability and fractional chromatic number, Discrete Math. 165/166 (1997), 31–38] proved that the choice ratio is equal to the fractional chromatic number, for every graph $G$. In this paper we prove that the analogous statement holds for the fractional $P$-chromatic number and the $P$-choice-ratio of $G$, where $P$ is any hereditary graph property. A generalization of these results for hypergraphs is presented, too.
Ako citovať:
ISO 690:
Mihók, P., Tuza, Z., Voigt, M. 1999. Fractional $P$-colourings and $P$-choice-ratio. In Tatra Mountains Mathematical Publications, vol. 18, no.4, pp. 69-77. 1210-3195.

APA:
Mihók, P., Tuza, Z., Voigt, M. (1999). Fractional $P$-colourings and $P$-choice-ratio. Tatra Mountains Mathematical Publications, 18(4), 69-77. 1210-3195.