# zbMATH — the first resource for mathematics

On connected coloring of graphs in prescribed colors. (Russian) Zbl 0931.05033
Suppose 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$$.

##### MSC:
 05C15 Coloring of graphs and hypergraphs 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
##### Keywords:
independence number; list coloring