Completing partial proper colorings using Hall's condition
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\) satisfies \textit{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 \textit{Hall} if \((G,L)\) satisfies Hall's condition. A graph \(G\) is \textit{Hall} \(m\)-{completable} for some \(m \geq \chi(G)\) if every partial proper \(m\)-coloring of \(G\) whose corresponding list assignment is Hall can be extended to a proper coloring of \(G\). In [Australas. J. Comb. 49, 127--151 (2011; Zbl 1228.05083)], \textit{B. B. Bobga} et al. posed the following questions: (1) Are there examples of graphs that are Hall \(m\)-completable, but not Hall \((m+1)\)-completable for some \(m \geq 3\)? (2) If \(G\) is neither complete nor an odd cycle, is \(G\) Hall \(\Delta(G)\)-completable? This paper establishes that for every \(m \geq 3\), there exists a graph that is Hall \(m\)-completable but not Hall \((m+1)\)-completable and also that every bipartite planar graph \(G\) is Hall \(\Delta(G)\)-completable.
- Characterization of graphs with hall number 2
- Colorings and orientations of graphs
- scientific article; zbMATH DE number 5944469 (Why is no real title available?)
- scientific article; zbMATH DE number 4208092 (Why is no real title available?)
- scientific article; zbMATH DE number 3735847 (Why is no real title available?)
- scientific article; zbMATH DE number 1151851 (Why is no real title available?)
- scientific article; zbMATH DE number 2200042 (Why is no real title available?)
This page was built for publication: Completing partial proper colorings using Hall's condition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2517653)
