Which Graphs Have Hall Number Two?

P.D. Johnson Jr.1, E.B. Wantland2
1Department of Discrete and Statistical Sciences Auburn University, AL 36849
2Mathematics Western College of the University of Montana Dillon, Montana

Abstract

We make further progress towards the forbidden-induced-subgraph characterization of the graphs with Hall number \(\leq 2\). We solve several problems posed in [4] and, in the process, describe all “partial wheel” graphs with Hall number \(\geq 2\) with every proper induced subgraph having Hall number \(\leq 2\).