The Hall number \(h(G)\) of a graph \(G\) is the minimum integer \(k\) such that every \(k\)-list assignment satisfying Hall’s condition on all induced subgraphs of \(G\) admits a proper coloring. In this paper, we investigate graphs for which the Hall number strictly captures list colorability, satisfying the equality \(h(G)=ch(G)\). We confirm a conjecture of Allagan by proving that this equality holds for every complete multipartite graph without singleton parts. For complete \(k\)-partite graphs of the form \(K(m,n,1,\dots,1)\), we establish that \(h(G)=ch(G)\) for all sufficiently large \(n\). Furthermore, we also determine \(h(G)\) for \(2\)-trees and wheel graphs \(W_n\). We show that for a \(2\)-tree \(G\), \(h(G) \in \{1, 2, 3\}\) for \(|V(G)| = 3, 4\), and \(\ge 5\), respectively. For wheel graphs, we demonstrate that \(h(W_n)\) is dictated by the parity of the rim: \(h(W_n)=3\) for odd \(n\ge5\), and \(h(W_n)=4\) for even \(n\ge6\).
All graphs considered are finite and simple. For a graph \(G\) we denote by \(V(G)\) and \(E(G)\) its vertex and edge sets, by \(\chi(G)\) its chromatic number, and by \(\alpha(G)\) its independence number. Recall that a graph is \(d\)-degenerate if every induced subgraph has a vertex of degree at most \(d\); equivalently, \(G\) admits an ordering of its vertices in which each vertex has at most \(d\) later neighbors. In particular, every \(d\)-degenerate graph satisfies \(\mathrm{ch}(G)\le d+1\).
In list coloring, each vertex \(v\) is assigned a finite set \(L(v)\) of admissible colors. An \(L\)-coloring is a proper coloring \(\varphi\) with \(\varphi(v)\in L(v)\) for all \(v\in V(G)\). The choice number (or list chromatic number) \(\mathrm{ch}(G)\) is the least integer \(k\) such that every assignment with \(|L(v)|\ge k\) for all \(v\) admits a proper coloring.
Let \(L\) be a list assignment and \(H\subseteq G\) an induced subgraph. For a color \(\sigma\), define \[H_\sigma \;:=\; H\bigl[\{v\in V(H):\sigma\in L(v)\}\bigr],\] the subgraph of \(H\) induced by the vertices whose lists contain \(\sigma\). Any proper \(L\)-coloring of \(H\) partitions \(V(H)\) into independent color classes \(C_\sigma\). Since \(|C_\sigma|\le \alpha(H_\sigma)\) for each \(\sigma\) and \(\sum\limits_\sigma |C_\sigma|=|V(H)|\), every proper \(L\)-coloring of \(H\) satisfies \[\label{eq:hall} \sum\limits_{\sigma}\alpha(H_\sigma)\;\ge\;|V(H)|. \tag{1}\]
Following Hilton and Johnson [8, 9], we call (1) Hall’s condition. Crucially, in the definition of \(h(G)\) below, Hall’s condition is required to hold for every induced subgraph \(H\subseteq G\), not merely for \(G\) itself. When \(G\) is complete, Hall’s condition is also sufficient and reduces to Hall’s classical theorem on systems of distinct representatives [7].
The Hall number \(h(G)\) is the least integer \(k\ge1\) such that every \(k\)-list assignment satisfying Hall’s condition on all induced subgraphs of \(G\) is colorable. Thus \(h(G)\) measures when the global obstruction encoded in (1) already guarantees list colorability, independent of local list-size constraints.
Hilton and Johnson [9] established the following basic facts:
(H1)\(h(G)\le \mathrm{ch}(G)\) for every graph \(G\);
(H2)if \(H\) is an induced subgraph of \(G\), then \(h(H)\le h(G)\);
(H3) if \(\mathrm{ch}(G)>\chi(G)\), then \(h(G)=\mathrm{ch}(G)\);
(H4) \(h(G)=1\) if and only if every block of \(G\) is complete.
In particular, strict inequality \(h(G)<\mathrm{ch}(G)\) can occur only in the borderline case \(\mathrm{ch}(G)=\chi(G)\). Classical examples illustrate the range: \(h(K_n)=1\) and \(h(T)=1\) for every tree, whereas \(h(C_n)=2\) for \(n\ge4\) [9]. At the other extreme, Tuza [11] proved the general bound \(h(G)\le\lfloor |V(G)|/2\rfloor\) and showed that deleting a single vertex may change \(h(G)\) by \(\Theta(|V(G)|)\).
A natural problem is to characterize graph classes for which \(h(G)=\mathrm{ch}(G)\). We resolve this question for three fundamental families: complete multipartite graphs, \(2\)-trees, and wheels. In these settings the equality is driven by distinct structural features: inheritance from multipartite cores, minimal induced Hall-tight obstructions together with bounded degeneracy in \(2\)-trees, and parity constraints in wheels. Together these results clarify when Hall’s condition captures the full content of list colorability.
Let \(K(n_1,\ldots,n_k)\) denote the complete \(k\)-partite graph with parts of sizes \(n_1,\ldots,n_k\). When \(n_i\ge2\) for all \(i\), we have \(\chi(G)=k\). The choice number of such graphs has been studied extensively, beginning with Erdős, Rubin, and Taylor and refined by Gravier–Maffray and Enomoto–Ohba–Ota–Sakamoto [3, 4, 6].
It was shown in [1] that \(h(K(m,2,\ldots,2))=\mathrm{ch}(K(m,2,\ldots,2))\) for all \(m\ge2\), and it was conjectured that the same equality holds whenever no part is a singleton. We confirm this and then determine when the equality persists once singleton parts are introduced.
Lemma 2.1. Let \(H\) be an induced subgraph of \(G\). If \(h(H)=\mathrm{ch}(G)=k\), then \(h(G)=k\).
Proof. By (H2), \(h(G)\ge h(H)=k\), while (H1) gives \(h(G)\le\mathrm{ch}(G)=k\). ◻
Theorem 2.2. If \(G=K(n_1,\ldots,n_k)\) with \(n_i\ge2\) for all \(i\), then \(h(G)=\mathrm{ch}(G)\).
Proof. If \(\mathrm{ch}(G)>\chi(G)=k\), then \(h(G)=\mathrm{ch}(G)\) by (H3). Otherwise \(\mathrm{ch}(G)=k\), and \(G\) contains an induced copy of the complete \(k\)-partite graph \(K(2,\ldots,2)\). By the Erdős–Rubin–Taylor theorem [4], \(\mathrm{ch}(K(2,\ldots,2))=k\). Since [1] establishes \(h(K(2,\ldots,2))=\mathrm{ch}(K(2,\ldots,2))\), we have \(h(K(2,\ldots,2))=k\). Lemma 2.1 yields \(h(G)=k\). ◻
Thus in the absence of singleton parts, equality is inherited from \(K(2,\ldots,2)\) and propagated by induced-subgraph monotonicity.
Lemma 2.3. If \(G\) contains an induced subgraph \(H\) with \(\mathrm{ch}(H)\ge\chi(G)+1\), then \(h(G)=\mathrm{ch}(G)\).
Proof. Since \(\mathrm{ch}(G)\ge\mathrm{ch}(H)\ge\chi(G)+1\), we have \(\mathrm{ch}(G)>\chi(G)\), and the conclusion follows from (H3). ◻
Consider \(G=K(m,n,1,\ldots,1)\), a complete \(k\)-partite graph with two nontrivial parts of sizes \(m\ge n\ge2\) and \(k-2\) singleton parts. Then \(\chi(G)=k\), and \(K_{m,n}\) appears as an induced subgraph.
Lemma 2.4. Fix \(m\ge2\) and set \(\displaystyle\lambda_m:=\log\!\left(\frac{m}{m-1}\right)\). For every \(\varepsilon\in(0,1)\) there exists \(n_0=n_0(m,\varepsilon)\) such that \(\displaystyle\mathrm{ch}(K_{m,n})\ge(1-\varepsilon)\frac{\log n}{\lambda_m}\) for all \(n\ge n_0\).
Proof. For fixed \(m\ge2\), Gazit and Krivelevich [5] establish \[\mathrm{ch}(K_{m,n})=\bigl(1+\eta(n)\bigr)\frac{\log n}{\lambda_m}, \qquad\eta(n)\to0\text{ as }n\to\infty,\] where all logarithms are natural. (The matching upper bound uses a probabilistic argument due to Alon [2].) Choosing \(n_0\) so that \(\eta(n)\ge-\varepsilon\) for \(n\ge n_0\) gives the stated lower bound. ◻
Theorem 2.5. Let \(G=K(m,n,1,\ldots,1)\) be a complete \(k\)-partite graph with \(m\ge n\ge2\) and \(k-2\) singleton parts. There exists an integer \(N=N(m,k)\) such that \(h(G)=\mathrm{ch}(G)\) for all \(n\ge N\).
Proof. By definition, \(\chi(G)=k\). Applying Lemma 2.4 with \(\varepsilon=\tfrac{1}{2}\), we obtain \(\mathrm{ch}(K_{m,n}) \ge \frac{\log n}{2\lambda_m}\) for all \(n \ge n_0(m,\tfrac{1}{2})\). Set \[N \;:=\; \max\!\left( n_0\!\left(m,\tfrac{1}{2}\right),\, \left\lceil e^{2k\lambda_m}\right\rceil + 1 \right).\]
For any \(n \ge N\), this choice ensures \(\frac{\log n}{2\lambda_m} > k\), and thus \(\mathrm{ch}(K_{m,n}) \ge k+1\). Since \(K_{m,n}\) is an induced subgraph of \(G\), monotonicity of the choice number yields \[\mathrm{ch}(G)\;\ge\;\mathrm{ch}(K_{m,n})\;\ge\; k+1\;>\;k=\chi(G).\]
Lemma 2.3 then yields \(h(G)=\mathrm{ch}(G)\). ◻
Corollary 2.6. For \(G=K_{n,\ldots,n}\) with \(k\ge2\) parts, \(h(G)=\mathrm{ch}(G)\) and, as \(n\to\infty\), \(\displaystyle\mathrm{ch}(G)=(1+o(1))\,\frac{\log n}{\log(k/(k-1))}\).
Proof. Equality \(h(G)=\mathrm{ch}(G)\) follows from Theorem 2.2, and the asymptotic formula is due to Gazit and Krivelevich [5]. ◻
A \(2\)-tree is obtained from \(K_3\) by repeatedly adjoining a new vertex adjacent to the endpoints of an existing edge. Equivalently, \(2\)-trees are precisely the edge-maximal chordal graphs of clique number three, or, in structural terms, the chordal graphs of treewidth two. In particular, every \(2\)-tree is \(2\)-degenerate; hence \[\mathrm{ch}(G)\le d(G)+1 \le 3.\]
We determine \(h(G)\) exactly for this class by identifying the minimal induced obstructions to Hall–colorability. The key observation is that every \(2\)-tree on at least five vertices contains, as an induced subgraph, one of the two nonisomorphic \(2\)-trees on five vertices: the fan \(F_4\) or the book \(B_3\). Each of these graphs admits a \(2\)-list assignment that satisfies Hall’s condition on every induced subgraph but admits no proper coloring. Consequently, \[h(F_4)=h(B_3)=3,\] and \(F_4\) and \(B_3\) serve as minimal Hall-tight obstructions within the class of \(2\)-trees.
Throughout this section we use the vertex labels \(\{a,b,c,d,e\}\) and list assignments shown in Figure 1. The corresponding vertex-deleted colorings, which verify Hall’s condition for all proper induced subgraphs, are recorded in Tables 1 and 2 in the Appendix.
The smallest cases are immediate. The unique \(2\)-tree on three vertices is \(K_3\), and \(h(K_3)=1\) by (H4). The unique \(2\)-tree on four vertices is the diamond \(K_4-e\); since it contains an induced \(C_4\), monotonicity (H2) gives \(h(K_4-e)\ge h(C_4)=2\), and the equality \(h(K_n-e)=n-2\) (see [9]) yields \(h(K_4-e)=2\).
Lemma 3.1. \(h(F_4)=3\).
Proof. Let \(a\) be the hub adjacent to the path \(b\)–\(c\)–\(d\)–\(e\), and assign \[L(a)=L(b)=L(e)=\{1,2\},\qquad L(c)=L(d)=\{1,3\}.\]
Since \(F_4\) is \(2\)-degenerate, \(\mathrm{ch}(F_4)\le3\), and (H1) gives \(h(F_4)\le3\). The following two claims establish \(h(F_4)\ge3\).
Claim 1.\(F_4\) admits no proper \(L\)-coloring.
Proof. If \(\varphi(a)=1\), every neighbor of \(a\) avoids \(1\), so \(\varphi(c)=\varphi(d)=3\), contradicting the edge \(c\)–\(d\). If \(\varphi(a)=2\), then \(\varphi(b)=\varphi(e)=1\), again forcing \(\varphi(c)=\varphi(d)=3\), a contradiction. ◻
Claim 2. class=”math inline”>\(L\) satisfies Hall’s condition on every induced subgraph of \(F_4\).
Proof. For the full graph, \((F_4)_1=F_4\), \((F_4)_2=F_4[\{a,b,e\}]\), and \((F_4)_3=F_4[\{c,d\}]\). Since \(b\) and \(e\) are nonadjacent, \(\alpha((F_4)_1)=2\), \(\alpha((F_4)_2)=2\), \(\alpha((F_4)_3)=1\), giving \(\sum\limits_\sigma\alpha((F_4)_\sigma)=5=|V(F_4)|\). Every proper induced subgraph of \(F_4\) is contained in \(F_4-v\) for some \(v\in V(F_4)\). Since a proper \(L\)-coloring of \(F_4-v\) satisfies Hall’s condition for all induced subgraphs thereof, it suffices to show one such coloring for each \(v\); these are recorded in Table 1. ◻
Claims 1 and 2 show that \(L\) satisfies Hall’s condition on every induced subgraph yet admits no proper coloring, so \(h(F_4)\ge3\), and hence \(h(F_4)=3\). ◻
Lemma 3.2. \(h(B_3)=3\).
Proof. Let \(B_3\) have spine edge \(ab\) and leaves \(c,d,e\), each adjacent to both \(a\) and \(b\), and assign \[L(a)=\{1,2\},\quad L(b)=\{1,3\},\quad L(c)=\{1,2\},\quad L(d)=\{1,3\},\quad L(e)=\{2,3\}.\] Since \(B_3\) is \(2\)-degenerate, \(\mathrm{ch}(B_3)\le3\), and (H1) gives \(h(B_3)\le3\). The following two claims establish \(h(B_3)\ge3\).
Claim 3. \(B_3\) admits no proper \(L\)-coloring.
Proof. Since \(L(a)\cap L(b)=\{1\}\), the spine assignments are in \(\{(1,3),(2,1),(2,3)\}\). Assignment \((1,3)\) exhausts \(L(d)\); \((2,1)\) exhausts \(L(c)\); \((2,3)\) exhausts \(L(e)\). ◻
Claim 4. \(L\) satisfies Hall’s condition on every induced subgraph of \(B_3\).
Proof. For the full graph, \((B_3)_1=B_3[\{a,b,c,d\}]\), \((B_3)_2=B_3[\{a,c,e\}]\), \((B_3)_3=B_3[\{b,d,e\}]\). In each case the two leaves present are nonadjacent, so \(\alpha((B_3)_\sigma)=2\) for each \(\sigma\), giving \(\sum\limits_\sigma\alpha((B_3)_\sigma)=6\ge5=|V(B_3)|\). Every proper induced subgraph of \(B_3\) is contained in \(B_3-v\) for some \(v\in V(B_3)\). Since a proper \(L\)-coloring of \(B_3-v\) satisfies Hall’s condition for all induced subgraphs thereof, it suffices to show one such coloring for each \(v\); these are recorded in Table 2. ◻
Claims 3 and 4 show that \(L\) satisfies Hall’s condition on every induced subgraph yet admits no proper coloring, so \(h(B_3)\ge3\), and hence \(h(B_3)=3\). ◻
Lemma 3.3. Every \(2\)-tree on \(n\ge5\) vertices contains an induced copy of \(F_4\) or \(B_3\).
Proof. Induct on \(n\). For \(n=5\), start from the unique \(2\)-tree on four vertices, the diamond on \(\{a,b,c,d\}\) with triangles \(abc\) and \(acd\) (so the shared edge is \(ac\)). A \(5\)-vertex \(2\)-tree is obtained by adjoining a new vertex \(e\) adjacent to the ends of some edge of this diamond. There are only two cases, up to symmetry.
(i) \(e\) attached to the shared edge \(ac\). Then \(e\) is adjacent to \(a\) and \(c\), and the three vertices \(b,d,e\) are pairwise nonadjacent, each adjacent to both \(a\) and \(c\). Hence the resulting graph is the book \(B_3\) (as in Figure 1).
(ii) \(e\) attached to a boundary edge (say \(ab\)). Then \(a\) is adjacent to \(b,c,d,e\), and the remaining edges among \(\{b,c,d,e\}\) are exactly \(bc,cd,de\), so \(\{b,c,d,e\}\) induces the path \(b\)–\(c\)–\(d\)–\(e\). Hence the resulting graph is the fan \(F_4\) (as in Figure 1). Thus the only \(2\)-trees on five vertices are \(F_4\) and \(B_3\).
For \(n>5\), write \(G\) as \(G'+v\) where \(G'\) is a \(2\)-tree on \(n-1\) vertices and \(v\) is adjacent precisely to the ends of some edge of \(G'\). By induction, \(G'\) contains an induced copy of \(F_4\) or \(B_3\), which remains induced in \(G\) since \(v\notin V(G')\). ◻
Theorem 3.4. Let \(G\) be a \(2\)-tree on \(n\) vertices. Then \[h(G)= \begin{cases} 1, & n=3,\\ 2, & n=4,\\ 3, & n\ge5. \end{cases}\]
Proof. The cases \(n=3\) and \(n=4\) were established above. For \(n\ge5\), Lemma 3.3 provides an induced copy of \(F_4\) or \(B_3\) in \(G\), each with \(h=3\) by Lemmas 3.1 and 3.2. Property (H2) gives \(h(G)\ge3\), while \(2\)-degeneracy and (H1) yield \(h(G)\le\mathrm{ch}(G)\le3\). ◻
Corollary 3.5.Every \(2\)-tree on at least five vertices satisfies \(h(G)=\mathrm{ch}(G)=3\).
Proof. Since \(G\) contains a triangle, \(\chi(G)\ge3\). The \(2\)-degeneracy bound gives \(\mathrm{ch}(G)\le3\), so \(\mathrm{ch}(G)=3\), and Theorem 3.4 gives \(h(G)=3\). ◻
Let \(W_n\) denote the wheel on \(n\ge4\) vertices, obtained from the cycle \(C_{n-1}\) by adjoining a universal vertex \(x\). Note that \(n\) odd corresponds to an even rim \(C_{n-1}\), while \(n\) even corresponds to an odd rim \(C_{n-1}\); this parity distinction governs all three cases below.
Theorem 4.1. For \(n\ge4\), \[h(W_n)= \begin{cases} 1, & n=4,\\ 3, & n\ge5\text{ odd},\\ 4, & n\ge6\text{ even}. \end{cases}\]
Proof. Since \(W_4\cong K_4\), property (H4) gives \(h(W_4)=1\). Label the rim vertices \(v_1,v_2,\ldots,v_{n-1}\) consecutively.
Case 1. \(n=2t+1\) odd, \(t\ge2\).
Since the rim \(C_{2t}\) is an even cycle, \(\chi(W_n)=3\). To see that \(\mathrm{ch}(W_n)=3\), consider any \(3\)-assignment of the vertices of \(W_n\). Color the hub \(x\) with any color \(c\in L(x)\) and remove \(c\) from each adjacent rim list; the residual lists have size at least \(2\) on \(C_{2t}\), and even cycles are \(2\)-choosable [4], so a proper coloring exists. Hence \(\mathrm{ch}(W_n)\le3\), and equality \(\mathrm{ch}(W_n)=3\) follows from \(\chi(W_n)=3\). By (H1), \(h(W_n)\le3\).
It therefore suffices to exhibit a \(2\)-assignment \(L\) that satisfies Hall’s condition on every induced subgraph of \(W_n\) yet admits no proper \(L\)-coloring. Set \(u:=v_{2t-1}\) and \(w:=v_{2t}\) as the last two rim vertices, so that the rim path is \(v_1\)–\(v_2\)–\(\cdots\)–\(v_{2t-2}\)–\(u\)–\(w\)–\(v_1\). Set \(L(x)=\{1,2\}\), \(L(u)=\{3,4\}\), \(L(w)=\{1,4\}\), and for \(1\le i\le 2t-2\), \[L(v_i)= \begin{cases} \{1,2\}, & i\text{ odd},\\ \{1,3\}, & i\text{ even}. \end{cases}\]
The four colors partition the vertex set as follows: \(V_\sigma\) consists of all rim vertices whose lists contain color \(\sigma\), together with \(x\) if \(\sigma\in L(x)\). Explicitly, \[\begin{aligned} V_1 &:= V(W_n)\setminus\{u\}, & V_2 &:= \{x\}\cup\{v_i: 1\le i\le 2t-3,\, i\text{ odd}\},\\ V_4 &:= \{u,w\}, & V_3 &:= \{u\}\cup\{v_i: 2\le i\le 2t-2,\, i\text{ even}\}. \end{aligned}\]
Claim 5. \(W_n\) admits no proper \(L\)-coloring.
Proof. If \(\varphi(x)=1\), every rim vertex avoids \(1\); for \(2\le i\le2t-2\) this forces \(\varphi(v_i)=3\) for even \(i\) and \(\varphi(v_i)=2\) for odd \(i\), so \(\varphi(v_{2t-2})=3\). Then \(\varphi(u)=4\) (since \(L(u)=\{3,4\}\) and \(v_{2t-2}\) is colored \(3\)), but \(w\) must avoid both \(1\) (hub spoke) and \(4\) (rim edge \(uw\)), exhausting its list \(\{1,4\}\), a contradiction. If \(\varphi(x)=2\), then \(\varphi(v_1)=1\). The same propagation gives \(\varphi(v_{2t-2})=3\), hence \(\varphi(u)=4\) and \(\varphi(w)=1\), which contradicts the rim edge \(wv_1\) since \(\varphi(v_1)=1\). ◻
Claim 6. \(L\) satisfies Hall’s condition on every induced subgraph of \(W_n\).
Proof. For an induced subgraph \(H=W_n[S]\) and \(\sigma\in\{1,2,3,4\}\), let \(H_\sigma:=H[S\cap V_\sigma]\). Since \(V_2\setminus\{x\}\) is independent and \(x\) is adjacent to all its members, \(\alpha(H_2)=\max(\mathbf{1}_{x\in S},|S\cap(V_2\setminus\{x\})|)\). Since \(H_4\) is an induced subgraph of the edge \(uw\), \(\alpha(H_4)=\min(1,|S\cap\{u,w\}|)\). As \(V_3\setminus\{u\}\) is independent on the rim and \(w\notin V_3\), \[\alpha(H_3)=|S\cap(V_3\setminus\{u\})|+\mathbf{1}_{[u\in S,\,v_{2t-2}\notin S]}.\]
We verify \(\sum\limits_{\sigma=1}^{4}\alpha(H_\sigma)\ge|S|\) in three cases.
Case (i). \(x\notin S\).
Then \(|S|=|S\cap(V_2\setminus\{x\})|+|S\cap(V_3\setminus\{u\})| +|S\cap\{u,w\}|\). With \(\alpha(H_2)=|S\cap(V_2\setminus\{x\})|\) and \(\alpha(H_3)\ge|S\cap(V_3\setminus\{u\})|\), it suffices to cover \(|S\cap\{u,w\}|\). If \(|S\cap\{u,w\}|\le1\) then \(\alpha(H_4)\) suffices. If \(u,w\in S\), then \(w\in V_1\) gives \(\alpha(H_1)\ge1\), so \(\alpha(H_1)+\alpha(H_4)\ge2\).
Case (ii). \(x\in S\), \(S\cap(V_2\setminus\{x\})=\emptyset\).
Then \(S\setminus\{x\}\subseteq(V_3\setminus\{u\})\cup\{u,w\}\), and \(S\cap(V_3\setminus\{u\})\) together with \(\{w\}\cap S\) form an independent set in \(H_1-x\), so \(\alpha(H_1)\ge|S\cap(V_3\setminus\{u\})|+\mathbf{1}_{[w\in S]}\). Summing with \(\alpha(H_2)=1\) and \(\alpha(H_4)\ge\mathbf{1}_{[u\in S]}\) gives \(\alpha(H_1)+\alpha(H_2)+\alpha(H_4)\ge |S\cap(V_3\setminus\{u\})|+\mathbf{1}_{[w\in S]}+1+\mathbf{1}_{[u\in S]}=|S|\).
Case (iii). \(x\in S\), \(S\cap(V_2\setminus\{x\})\ne\emptyset\).
Here \(\alpha(H_2)=|S\cap(V_2\setminus\{x\})|\) and \(\alpha(H_1)\ge1\). It suffices to show \(\alpha(H_1)+\mathbf{1}_{[u\in S,\,v_{2t-2}\notin S]} +\min(1,|S\cap\{u,w\}|)\ge1+|S\cap\{u,w\}|\). If \(|S\cap\{u,w\}|\le1\) this follows from \(\alpha(H_1)\ge1\). If \(u,w\in S\) and \(v_{2t-2}\notin S\), the indicator provides \(+1\). If \(u,w,v_{2t-2}\in S\), then \(u\notin V_1\) makes \(v_{2t-2}\) and \(w\) nonadjacent in \(H_1-x\), yielding \(\alpha(H_1)\ge2\). ◻
Claims 5 and 6 give \(h(W_n)\ge3\), completing Case 1.
Case 2. \(n=2t\) even, \(t\ge3\).
The rim \(C_{2t-1}\) is an odd cycle, so \(\chi(W_n)=4\). Every induced subgraph \(H\subseteq W_n\) contains a vertex of degree at most \(3\): if \(x\notin V(H)\) then \(H\) is a subgraph of \(C_{2t-1}\) and every vertex has degree at most \(2\); if \(x\in V(H)\) every rim vertex has at most two rim-neighbors and one spoke. Hence \(W_n\) is \(3\)-degenerate, and \(\mathrm{ch}(W_n)\le d(W_n)+1\le 4\) [4]. As \(\chi(W_n)=4\), we have \(\mathrm{ch}(W_n)=4\), and (H1) yields \(h(W_n)\le4\).
Claim 7. \(W_n\) is not \(3\)-colorable.
Proof. Immediate from \(\chi(W_n)=4>3\). ◻
Claim 8. The uniform assignment \(L(v)=\{1,2,3\}\) for all \(v\in V(W_n)\) satisfies Hall’s condition on every induced subgraph of \(W_n\).
Proof. Since every vertex carries the same list, \(H_\sigma=H\) for each \(\sigma\), and Hall’s condition reduces to \(3\alpha(H)\ge|V(H)|\). For a proper induced subgraph \(H\subsetneq W_n\), we have \(\chi(H)\le3\): if \(x\notin V(H)\), then \(H\) is an induced subgraph of \(C_{2t-1}\), hence a disjoint union of paths, which is \(2\)-colorable; if \(x\in V(H)\), then \(H-x\) is an induced subgraph of a path, hence bipartite, so \(H\) is \(3\)-colorable. In either case \(\alpha(H)\ge|V(H)|/\chi(H)\ge|V(H)|/3\). For \(H=W_n\), \(\alpha(W_n)=\alpha(C_{2t-1})=t-1\), so \(3\alpha(W_n)=3t-3\ge2t=|V(W_n)|\) for \(t\ge3\). ◻
Claims 7 and 8 together show that \(L(v)=\{1,2,3\}\) satisfies Hall’s condition on every induced subgraph of \(W_n\) (including \(W_n\) itself) yet \(W_n\) is not \(L\)-colorable, so \(h(W_n)\ge4\), and hence \(h(W_n)=4\). ◻
The results obtained here isolate three distinct structural sources governing the identity \(h(G)=\mathrm{ch}(G)\).
For complete multipartite graphs \(K(n_1,\ldots,n_k)\) with all parts of size at least \(2\), the equality is inherited from the induced core \(K(2,\ldots,2)\) and lifted to the full graph via induced-subgraph monotonicity (H2). Thus in this setting Hall–colorability is controlled by a rigid multipartite kernel.
For \(2\)-trees, the mechanism is obstruction-based. The five-vertex graphs \(F_4\) and \(B_3\) (Figure 1) constitute the minimal induced Hall-tight configurations. Every \(2\)-tree on at least five vertices contains one of these as an induced subgraph, forcing \(h(G)\ge3\), while \(2\)-degeneracy ensures \(\mathrm{ch}(G)\le3\). Here equality emerges from the interplay between minimal induced obstructions and bounded degeneracy.
For wheels, parity governs the outcome. If the rim is even (\(n\) odd), then \(W_n\) is \(3\)-choosable and \(h(W_n)=\mathrm{ch}(W_n)=3\). If the rim is odd (\(n\) even), the uniform \(3\)-assignment satisfies Hall’s condition on every induced subgraph, including \(W_n\) itself, yet \(W_n\) is not \(3\)-colorable; hence \(h(W_n)=4=\mathrm{ch}(W_n)\). In this case Hall’s condition detects precisely the chromatic obstruction created by the odd rim.
To summarize, we established exact Hall numbers for all \(2\)-trees and all wheel graphs, proves \(h(G)=\mathrm{ch}(G)\) for every complete multipartite graph without singleton parts, and proves the eventual equality \(h(G)=\mathrm{ch}(G)\) for \(K(m,n,1,\ldots,1)\) as \(n\to\infty\).
These examples suggest several natural directions. For \(k\)-trees, does there exist a threshold \(n_0(k)\) such that \(h(G)=\mathrm{ch}(G)=k+1\) for every \(k\)-tree \(G\) with \(|V(G)|\ge n_0(k)\)? More generally, can a chordal graph satisfy \(h(G)<\mathrm{ch}(G)\)? Ohba’s theorem [10] asserts that \(\mathrm{ch}(G)=\chi(G)\) whenever \(|V(G)|\le 2\chi(G)+1\). Whether an analogous sharp bound forces \(h(G)=\chi(G)\) remains an open problem.
The following tables record the proper \(L\)-colorings used in Claims 2 and 4. Each row gives an explicit proper \(L\)-coloring of the induced subgraph \(G-v\) under the list assignment defined in the corresponding lemma; a dash indicates the deleted vertex.
| Subgraph | \(\varphi(a)\) | \(\varphi(b)\) | \(\varphi(c)\) | \(\varphi(d)\) | \(\varphi(e)\) |
|---|---|---|---|---|---|
| \(F_4-a\) | — | \(2\) | \(1\) | \(3\) | \(2\) |
| \(F_4-b\) | \(2\) | — | \(1\) | \(3\) | \(1\) |
| \(F_4-c\) | \(1\) | \(2\) | — | \(3\) | \(2\) |
| \(F_4-d\) | \(1\) | \(2\) | \(3\) | — | \(2\) |
| \(F_4-e\) | \(2\) | \(1\) | \(3\) | \(1\) | — |
| Subgraph | \(\varphi(a)\) | \(\varphi(b)\) | \(\varphi(c)\) | \(\varphi(d)\) | \(\varphi(e)\) |
|---|---|---|---|---|---|
| \(B_3-a\) | — | \(1\) | \(2\) | \(3\) | \(2\) |
| \(B_3-b\) | \(1\) | — | \(2\) | \(3\) | \(3\) |
| \(B_3-c\) | \(2\) | \(1\) | — | \(3\) | \(3\) |
| \(B_3-d\) | \(1\) | \(3\) | \(2\) | — | \(2\) |
| \(B_3-e\) | \(2\) | \(3\) | \(1\) | \(1\) | — |