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:
 [1] Alon, N., Choice numbers of graphs: A probabilistic approach, Combin. probab. comput., 1, 2, 107-114, (1992) · Zbl 0793.05076 [2] Alon, N., The strong chromatic number of a graph, Random structures algorithms, 3, 1, 1-7, (1992) · Zbl 0751.05034 [3] Alon, N., Restricted colorings of graphs, (), 1-33 · Zbl 0791.05034 [4] Alon, N.; Spencer, J.H., The probabilistic method, (), with an appendix on the life and work of Paul Erdős · Zbl 1333.05001 [5] Alon, N.; Tarsi, M., Colorings and orientations of graphs, Combinatorica, 12, 2, 125-134, (1992) · Zbl 0756.05049 [6] 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 [7] Bollobás, B., The chromatic number of random graphs, Combinatorica, 8, 1, 49-55, (1988) · Zbl 0666.05033 [8] Bollobás, B., Random graphs, () · Zbl 1027.05083 [9] Chetwynd, A.; Häggkvist, R., A note on List-colorings, J. graph theory, 13, 1, 87-95, (1989) · Zbl 0674.05026 [10] Ellingham, M.N.; Goddyn, L., List edge colourings of some 1-factorable multigraphs, Combinatorica, 16, 3, 343-352, (1996) · Zbl 0860.05035 [11] Erdős, P.; Rubin, A.L.; Taylor, H., Choosability in graphs, () · Zbl 0469.05032 [12] 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 [13] Galvin, F., The List chromatic index of a bipartite multigraph, J. combin. theory ser. B, 63, 1, 153-158, (1995) · Zbl 0826.05026 [14] 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 [15] Golumbic, M.C., Algorithmic graph theory and perfect graphs, (), with a foreword by Claude Berge · Zbl 0365.05025 [16] S. Gutner, Choice numbers of graphs, Master’s Thesis, Tel Aviv University, 1992 [17] Gutner, S., The complexity of planar graph choosability, Discrete math., 159, 1-3, 119-130, (1996) · Zbl 0865.05066 [18] A.J. Harris, Problems and conjectures in extremal graph theory, Ph.D. Thesis, Cambridge University, UK, 1984 [19] Kratochvíl, J.; Tuza, Z.; Voigt, M., New trends in the theory of graph colorings: choosability and List coloring, (), 183-197 · Zbl 1025.05030 [20] Tuza, Z., Graph colorings with local constraints—a survey, Discuss. math. graph theory, 17, 2, 161-228, (1997) · Zbl 0923.05027 [21] Tuza, Z.; Voigt, M., Every 2-choosable graph is $$(2 m, m)$$-choosable, J. graph theory, 22, 3, 245-252, (1996) · Zbl 0853.05034 [22] 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.