zbMATH — the first resource for mathematics

List-colourings of graphs. (English) Zbl 0606.05027
The edge list-chromatic number, \(\chi '_{\ell}(G)\), of a graph G is the minimum among lengths \(| \Lambda (\alpha)|\) of lists \(\Lambda(\alpha)\), \(\alpha\in E(G)\), which guarantees the existence of an edge-colouring \(\phi: E(G)\to \cup_{\alpha}\Lambda(\alpha)\) with \(\phi(\alpha)\in \Lambda(\alpha)\) for each \(\alpha\in E(G)\). The authors show that there is a \(c<2\) such that \(\chi'_{\ell}(G)\leq c\Delta\) provided the maximal degree \(\Delta\) of G is large. Same holds for a total chromatic number \(\chi^*(G)\) because \(\chi^*(G)\leq \chi'_{\ell}(G)+2\). Chromatic numbers of r-uniform hypergraphs (possibly with maximal degree \(\Delta)\) are estimated.
Reviewer: Z.Skupień

05C15 Coloring of graphs and hypergraphs
05C65 Hypergraphs
Full Text: DOI
[1] Albertson, M.O., Berman, D.M.: Cliques, colourings and locally perfect graphs. In: Proc. South-Eastern Conference in Combinatorics, Graph Theory and Computing, Boca Raton 1983 · Zbl 0576.05024
[2] Behzad, M.: The total chromatic number of a graph. In: A Survey; Combinatorial Mathematics and its Applications (Proc. Conf. Oxford 1969), pp. 1–8. London: Academic Press 1971 · Zbl 0221.05062
[3] Berge, C.: Graphs and Hypergraphs. Amsterdam: North-Holland 1973 · Zbl 0254.05101
[4] Bollobás, B.: A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. Europ. J. Comb.1, 311–316 (1980) · Zbl 0457.05038
[5] Bollobás, B.: Random Graphs. London-New York: Academic Press (in press) · Zbl 0752.05044
[6] Erdös, P., Lovász, L.: Problems and results on 3-chromatic hypergraphs and some related results. In: Infinite and Finite Sets (Proc. Colloq. Keszthely, Hungary 1973, edited by A. Hajnal, R. Rado, V.T. Sós, vol. II. pp. 609–627.) Colloq. Math. Soc. Janos Bolyai10 (1975)
[7] Erdös, P., Rubin, A.L., Taylor, H.: Choosability in graphs. In: Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, pp. 125–157. Arcata: Humboldt State Univ. 1979
[8] Harris, A.J.: Problems and conjectures in extremal graph theory. Ph.D. dissertation, Cambridge Univ. 1984
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.