On connected coloring of graphs in prescribed colors.

*(Russian)*Zbl 0931.05033Suppose each vertex \(v\) of a graph \(G\) is assigned a set \(A(v)\) of admissible colors. Then a connected list vertex coloring of \(G\) is a decomposition of its vertices into subsets, called color classes, such that the color \(c(v)\) of \(v\) belongs to \(A(v)\) for each \(v\in V(G)\) and each color class induces a connected subgraph of \(G\). The symbol \(\alpha(G)\) denotes the minimum \(k\) such that \(G\) has a connected coloring whenever \(|A(v)|\geq k\) for each \(v\in V(G)\). In particular, it is proven that each \(G\) has \(\alpha(G)\) at least as large as its independence number \(\varepsilon(G)\), and if \(G\) is bipartite then \(\alpha(G)=\varepsilon(G)\). For the similarly defined connected list edge colorings of a multigraph \(G\), the analog of \(\alpha(G)\) is denoted by \(\beta(G)\). The main result asserts that, if each connected component of \(G\) has an even number of edges, then \(\beta(G)\leq |E(G)|/2\). Let \(\pi(G)\) be the edge independence number of a multigraph \(G\). It is conjectured that \(\beta(G)\leq \max\{\pi(G),|E(G)|/2\}\) for each \(G\).

Reviewer: O.V.Borodin (Novosibirsk)