Some results on (a:b)-choosability

Details Some results on (a:b)-choosability Some results on (a:b)-choosability

2008-02-10

arxiv.org/abs/0802.1338v1

Computer Science

Discrete Mathematics

Scientific paper

A solution to a problem of Erd\H{o}s, Rubin and Taylor is obtained by showing that if a graph $G$ is $(a:b)$-choosable, and $c/d > a/b$, then $G$ is not necessarily $(c:d)$-choosable. Applying probabilistic methods, an upper bound for the $k^{th}$ choice number of a graph is given. We also prove that a directed graph with maximum outdegree $d$ and no odd directed cycle is $(k(d+1):k)$-choosable for every $k \geq 1$. Other results presented in this article are related to the strong choice number of graphs (a generalization of the strong chromatic number). We conclude with complexity analysis of some decision problems related to graph choosability.

Affiliated with

Also associated with

No associations

Rating

Some results on (a:b)-choosability does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Some results on (a:b)-choosability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Some results on (a:b)-choosability will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-295578