
doi: 10.37236/4387
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 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 $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 2011, 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.
list coloring, Coloring of graphs and hypergraphs, Hall's condition, partial proper coloring, Hall \(m\)-completable, Hall number
list coloring, Coloring of graphs and hypergraphs, Hall's condition, partial proper coloring, Hall \(m\)-completable, Hall number
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
