# zbMATH — the first resource for mathematics

Some results on $$(a:b)$$-choosability. (English) Zbl 1198.05049
Summary: A solution to a problem of P. Erdős, A.L. Rubin, and H. Taylor [“Choosability in graphs,” Combinatorics, graph theory and computing, Proc. West Coast Conf., Arcata/Calif. 1979, 125–157 (1980; Zbl 0469.05032)] 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.

##### MSC:
 05C15 Coloring of graphs and hypergraphs
Full Text:
##### References:
  Alon, N., Choice numbers of graphs: A probabilistic approach, Combin. probab. comput., 1, 2, 107-114, (1992) · Zbl 0793.05076  Alon, N., The strong chromatic number of a graph, Random structures algorithms, 3, 1, 1-7, (1992) · Zbl 0751.05034  Alon, N., Restricted colorings of graphs, (), 1-33 · Zbl 0791.05034  Alon, N.; Spencer, J.H., The probabilistic method, (), with an appendix on the life and work of Paul Erdős · Zbl 1333.05001  Alon, N.; Tarsi, M., Colorings and orientations of graphs, Combinatorica, 12, 2, 125-134, (1992) · Zbl 0756.05049  Berge, C., Graphs and hypergraphs, (1973), North-Holland Publishing Co. Amsterdam, translated from the French by Edward Minieka, North-Holland Mathematical Library, vol. 6 · Zbl 0483.05029  Bollobás, B., The chromatic number of random graphs, Combinatorica, 8, 1, 49-55, (1988) · Zbl 0666.05033  Bollobás, B., Random graphs, () · Zbl 1027.05083  Chetwynd, A.; Häggkvist, R., A note on List-colorings, J. graph theory, 13, 1, 87-95, (1989) · Zbl 0674.05026  Ellingham, M.N.; Goddyn, L., List edge colourings of some 1-factorable multigraphs, Combinatorica, 16, 3, 343-352, (1996) · Zbl 0860.05035  Erdős, P.; Rubin, A.L.; Taylor, H., Choosability in graphs, () · Zbl 0469.05032  Fleischner, H.; Stiebitz, M., A solution to a colouring problem of P. Erdős, Discrete math., 101, 1-3, 39-48, (1992), special volume to mark the centennial of Julius Petersen’s “Die Theorie der regulären Graphs”, Part II · Zbl 0759.05037  Galvin, F., The List chromatic index of a bipartite multigraph, J. combin. theory ser. B, 63, 1, 153-158, (1995) · Zbl 0826.05026  Garey, M.R.; Johnson, D.S., Computers and intractability, (1979), W.H. Freeman and Co. San Francisco, Calif, a guide to the theory of NP-completeness, A Series of Books in the Mathematical Sciences · Zbl 0411.68039  Golumbic, M.C., Algorithmic graph theory and perfect graphs, (), with a foreword by Claude Berge · Zbl 0365.05025  S. Gutner, Choice numbers of graphs, Master’s Thesis, Tel Aviv University, 1992  Gutner, S., The complexity of planar graph choosability, Discrete math., 159, 1-3, 119-130, (1996) · Zbl 0865.05066  A.J. Harris, Problems and conjectures in extremal graph theory, Ph.D. Thesis, Cambridge University, UK, 1984  Kratochvíl, J.; Tuza, Z.; Voigt, M., New trends in the theory of graph colorings: choosability and List coloring, (), 183-197 · Zbl 1025.05030  Tuza, Z., Graph colorings with local constraints—a survey, Discuss. math. graph theory, 17, 2, 161-228, (1997) · Zbl 0923.05027  Tuza, Z.; Voigt, M., Every 2-choosable graph is $$(2 m, m)$$-choosable, J. graph theory, 22, 3, 245-252, (1996) · Zbl 0853.05034  Vizing, V.G., Coloring the vertices of a graph in prescribed colors, Diskret. analiz (29 metody diskret. anal. v teorii kodov i shem), 3-10, 101, (1976)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.