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\).

05C15 Coloring of graphs and hypergraphs
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)