Every graph \(G\) is Hall \(\Delta(G)\)-extendible (Q727195)

Summary: In the context of list coloring the vertices of a graph, Hall's condition is a generalization of Hall's Marriage Theorem and is necessary (but not sufficient) for a graph to admit a proper list coloring. The graph \(G\) with list assignment \(L\), abbreviated \((G,L)\), satisfies Hall's condition if for each subgraph \(H\) of \(G\), the inequality \(|V(H)| \leq \sum_{\sigma \in \mathcal{C}} \alpha(H(\sigma, L))\) is satisfied, where \(\mathcal{C}\) is the set of colors and \(\alpha(H(\sigma, L))\) is the independence number of the subgraph of \(H\) induced on the set of vertices having color \(\sigma\) in their lists. A list assignment \(L\) to a graph \(G\) is called Hall if \((G,L)\) satisfies Hall's condition. A graph \(G\) is Hall \(k\)-extendible for some \(k \geq \chi(G)\) if every \(k\)-precoloring of \(G\) whose corresponding list assignment is Hall can be extended to a proper \(k\)-coloring of \(G\). \textit{B. B. Bobga} et al. [Australas. J. Comb. 49, 127--151 (2011; Zbl 1228.05083)] posed the question: If \(G\) is neither complete nor an odd cycle, is \(G\) Hall \(\Delta(G)\)-extendible? This paper establishes an affirmative answer to this question: every graph \(G\) is Hall \(\Delta(G)\)-extendible. Results relating to the behavior of Hall extendibility under subgraph containment are also given. Finally, for certain graph families, the complete spectrum of values of \(k\) for which they are Hall \(k\)-extendible is presented. We include a focus on graphs which are Hall \(k\)-extendible for all \(k \geq \chi(G)\), since these are graphs for which satisfying the obviously necessary Hall's condition is also sufficient for a precoloring to be extendible.