Hall numbers of complete multipartite graphs, 2-trees, and wheels
Utilitas Mathematica · 10.05.2026 · 127 · 129-139
DOI: 10.61091/um127-09 ↗Kurz gefasst
Fachartikel in der Zeitschrift Utilitas Mathematica, online erschienen am 10.05.2026. Verfasst von Julian Allagan und 1 weiteren Autor:innen.
Abstract (Originalsprache)
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\).
Zitieren
APA
Allagan, J., & Pereyra, K. (2026). Hall numbers of complete multipartite graphs, 2-trees, and wheels. Utilitas Mathematica, 127, 129-139. https://doi.org/10.61091/um127-09
Vancouver
Allagan J, Pereyra K. Hall numbers of complete multipartite graphs, 2-trees, and wheels. Utilitas Mathematica. 2026;127:129-139. doi:10.61091/um127-09
BibTeX
@article{Allagan2026,
author = {Allagan, Julian and Pereyra, Kevin},
title = {Hall numbers of complete multipartite graphs, 2-trees, and wheels},
journal = {Utilitas Mathematica},
year = {2026},
volume = {127},
pages = {129--139},
doi = {10.61091/um127-09}
}
EUVIMED