List-colourings of graphs (Q1084403)

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.